Article

Robust sketched symbol fragmentation using templates

Authors:

Michael Shilman,

A. Richard NewtonAuthors Info & Claims

IUI '04: Proceedings of the 9th international conference on Intelligent user interfaces

Pages 156 - 160

https://doi.org/10.1145/964442.964472

Published: 13 January 2004 Publication History

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]

Apte, A., Vo, V. and Kimura, T.D., Recognizing Multistroke Geometric Shapes: An Experimental Evaluation. in UIST 1993, (Atlanta Georgia, 1993), ACM Press, 121--128.

Digital Library

[3]

Bellman, R. On the Approximation of Curves by Line Segments using Dynamic Programming. Commun. ACM, 4 (6). 284.

Digital Library

[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]

Duda, R.O. and Hart, P.E. Pattern Classification and Scene Analysis. Wiley Press, New York, 1973.

Digital Library

[7]

Fischler, M.A. and Bolles, R.C. Perceptual Organization and Curve Partitioning. IEEE Trans. PAMI, 8 (1). 100--105.

Digital Library

[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]

Hearst, M.A., Gross, M.D., Landay, J.A. and Stahovich, T.F. Sketching Intelligent Systems. IEEE Intelligent System, 3 (3). 10--19.

Digital Library

[10]

Hong, J.I. and Landay, J.A. SATIN: A Toolkit for Informal Ink-based Applications. CHI Letters: ACM Symposium on User Interface Software and Technology: UIST 2000, 2 (2). 63--72.

Digital Library

[11]

Igarashi, T., Matsuoka, S., Kawachiya, S. and Tanaka, H., Interactive Beautification: a Technique for Rapid Geometric Design. in UIST 1997, (Canada, 1997), 105--114.

Digital Library

[12]

Landay, J.A. and Myers, B.A. Sketching Interfaces: Toward More Human Interface Design. IEEE Computer, 34 (3). 56--64.

Digital Library

[13]

Lin, J., Newman, M.W., Hong, J.I. and Landay, J.A. DENIM: Finding a Tighter Fit between Tools and Practice for Web Site Design. CHI Letters: ACM Symposium on User Interface Software and Technology: UIST 2000, 2 (1). 510--517.

Digital Library

[14]

Lipscomb, J.S. A Trainable Gesture Recognizer. Pattern Recognition, 24 (9). 895--907.

Digital Library

[15]

Long, A.C., Landay, J.A. and Rowe, L.A. Visual Similarity of Pen Gestures. CHI Letters: ACM Symposium on User Interface Software and Technology: UIST 2000, 2 (1). 360--367.

Digital Library

[16]

Pavlidis, T. Curve Fitting with Conic Splines. ACM Trans. on Graphics, 2 (1). 1--31.

Digital Library

[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]

Pilu, M., Fitzgibbon, A. and Fisher, R. Direct Least-Square Fitting of Ellipses. IEEE Trans. PAMI, 21 (5). 476--480.

Digital Library

[20]

Rubine, D. Specifying Gestures by Example. SIGGRAPH '91, 25 (4). 329--337.

Digital Library

[21]

Saund, E. Finding Perceptually Closed Paths in Sketches and Drawings. IEEE Transactions on Pattern Analysis and Machine Intelligence, 25 (4). 475--491.

Digital Library

[22]

Saund, E. and Moran, T., A Perceptually Supported Sketch Editor. in UIST 1994, (Marina del Rey CA, 1994), ACM Press, 175--184.

Digital Library

[23]

Sezgin, T.M., Stahovich, T. and Davis, R., Sketch Based Interfaces: Early Processing for Sketch Understanding. in PUI 2001, (Orlando FL, 2001), ACM Press.

Digital Library

[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]

West, G. and Rosin, P. Techniques for Segmenting Image Curves into Meaningful Descriptions. Pattern Recognition, 24 (7). 643--152.

Digital Library

[27]

Yu, B., Recognition of Freehand Sketches using Mean Shift. in IUI 2003, (Miami FL, 2003), 204--210.

Digital Library

Cited By

Magrofuoco NRoselli PVanderdonckt J(2022)µV: An Articulation, Rotation, Scaling, and Translation Invariant (ARST) Multi-stroke Gesture RecognizerProceedings of the ACM on Human-Computer Interaction10.1145/35322006:EICS(1-25)Online publication date: 17-Jun-2022
https://dl.acm.org/doi/10.1145/3532200
Magrofuoco NRoselli PVanderdonckt J(2021)Two-dimensional Stroke Gesture RecognitionACM Computing Surveys10.1145/346540054:7(1-36)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465400
Magrofuoco NRoselli PVanderdonckt JPérez-Medina JVatavu RPanach IVanderdonckt JPastor Ó(2019)GestManProceedings of the ACM SIGCHI Symposium on Engineering Interactive Computing Systems10.1145/3319499.3328227(1-6)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3319499.3328227
Show More Cited By

Index Terms

Robust sketched symbol fragmentation using templates
1. Computing methodologies
  1. Artificial intelligence
    1. Computer vision
      1. Computer vision problems
        Interest point and salient region detections

Recommendations

Recognition and beautification of multi-stroke symbols in digital ink

Sketch-based user interfaces (UIs) provide a more direct and convenient way for interacting with computers, especially for performing graphical tasks. Most computer programs provide a mouse-and-palette-based UI for editing shapes, which can be ...
A dynamic stroke segmentation technique for sketched symbol recognition
IbPRIA'05: Proceedings of the Second Iberian conference on Pattern Recognition and Image Analysis - Volume Part II

In this paper, we address the problem of ink parsing, which tries to identify distinct symbols from a stream of pen strokes. An important task of this process is the segmentation of the users' pen strokes into salient fragments based on geometric ...
Multi-Linguistic Optical Font Recognition Using Stroke Templates
ICPR '06: Proceedings of the 18th International Conference on Pattern Recognition - Volume 02

One of the essential distinctions between different fonts is their stroke shape. A method is presented to automatically extract representative stroke templates from a text image, which contains characters of the same typeface. The collected stroke ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

IUI '04: Proceedings of the 9th international conference on Intelligent user interfaces

January 2004

396 pages

ISBN:1581138156

DOI:10.1145/964442

Conference Chair:
Jean Vanderdonckt
University Louvain (BE)
,
Program Chairs:
Nuno Jardim Nunes
University of Madeira (PT)
,
Charles Rich
Mitsubishi Electric Research Laboratories (US)

Copyright © 2004 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 13 January 2004

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

IUI-CADUI04

Sponsor:

IUI-CADUI04: Intelligent User Interface

January 13 - 16, 2004

Funchal, Madeira, Portugal

Acceptance Rates

IUI '04 Paper Acceptance Rate 72 of 140 submissions, 51%;

Overall Acceptance Rate 746 of 2,811 submissions, 27%

Upcoming Conference

IUI '25

Sponsor:
sigai
sigai

30th International Conference on Intelligent User Interfaces

March 24 - 27, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

33
Total Citations
View Citations
664
Total Downloads

Downloads (Last 12 months)1
Downloads (Last 6 weeks)0

Reflects downloads up to 15 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

Magrofuoco NRoselli PVanderdonckt J(2022)µV: An Articulation, Rotation, Scaling, and Translation Invariant (ARST) Multi-stroke Gesture RecognizerProceedings of the ACM on Human-Computer Interaction10.1145/35322006:EICS(1-25)Online publication date: 17-Jun-2022
https://dl.acm.org/doi/10.1145/3532200
Magrofuoco NRoselli PVanderdonckt J(2021)Two-dimensional Stroke Gesture RecognitionACM Computing Surveys10.1145/346540054:7(1-36)Online publication date: 18-Jul-2021
https://dl.acm.org/doi/10.1145/3465400
Magrofuoco NRoselli PVanderdonckt JPérez-Medina JVatavu RPanach IVanderdonckt JPastor Ó(2019)GestManProceedings of the ACM SIGCHI Symposium on Engineering Interactive Computing Systems10.1145/3319499.3328227(1-6)Online publication date: 18-Jun-2019
https://dl.acm.org/doi/10.1145/3319499.3328227
Vanderdonckt JRoselli PPérez-Medina JD'Mello SGeorgiou PScherer SProvost ESoleymani MWorsley M(2018)!FTL, an Articulation-Invariant Stroke Gesture Recognizer with Controllable Position, Scale, and Rotation InvariancesProceedings of the 20th ACM International Conference on Multimodal Interaction10.1145/3242969.3243032(125-134)Online publication date: 2-Oct-2018
https://dl.acm.org/doi/10.1145/3242969.3243032
Murugappan SPiya CYang MRamani K(2017)FEAsy: A Sketch-Based Tool for Finite Element AnalysisJournal of Computing and Information Science in Engineering10.1115/1.403438717:3Online publication date: 16-Feb-2017
https://doi.org/10.1115/1.4034387
Wenyin LLu TYajie YLiang SZhang R(2013)Online stroke segmentation by quick penalty‐based dynamic programmingIET Computer Vision10.1049/iet-cvi.2012.02967:5(311-319)Online publication date: 1-Oct-2013
https://dl.acm.org/doi/10.1049/iet-cvi.2012.0296
Schmidt MWeber G(2013)Template based classification of multi-touch gesturesPattern Recognition10.1016/j.patcog.2013.02.00146:9(2487-2496)Online publication date: 1-Sep-2013
https://dl.acm.org/doi/10.1016/j.patcog.2013.02.001
Albert FFernáNdez-Pacheco DAleixos N(2013)New method to find corner and tangent vertices in sketches using parametric cubic curves approximationPattern Recognition10.1016/j.patcog.2012.11.00646:5(1433-1448)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1016/j.patcog.2012.11.006
Schmidt MWeber G(2013)Recognition of multi-touch drawn sketchesProceedings of the 15th international conference on Human-Computer Interaction: interaction modalities and techniques - Volume Part IV10.1007/978-3-642-39330-3_51(479-490)Online publication date: 21-Jul-2013
https://dl.acm.org/doi/10.1007/978-3-642-39330-3_51
Renau-Ferrer NRemi C(2012)Procedural Analysis of a Sketching Activity: Principles and Applications2012 International Conference on Frontiers in Handwriting Recognition10.1109/ICFHR.2012.255(461-466)Online publication date: Sep-2012
https://doi.org/10.1109/ICFHR.2012.255
Show More Cited By

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents