Revisiting ShortStraw: improving corner finding in sketch-based interfaces

ABSTRACT

We present IStraw, a new corner finding technique based on an analysis of the ShortStraw algorithm. Our analysis reveals several limitations in ShortStraw and we develop techniques to overcome them. We also present an extension to our corner finding approach for dealing with ink strokes that contain curves and arcs. An evaluation of our approach shows significant accuracy improvements over ShortStraw for polyline ink strokes with and without curves using an all-or-nothing accuracy metric while still maintaining ShortStraw's computational complexity.

References

1. {AD05} Allvarado C., Davis R.: Sketchread: A multi-domain sketch recognition engine. In UIST '04: Proceedings of the 17th annual ACM symposium on User interface software and technology (2005), vol. 29, pp. 518--532. 1
2. {FYH97} Fu A. M. N., Yan H., Huang K.: A curve bend function based method to characterize contour shapes. Pattern Recognition 30, 30 (1997), 1661--1671. 2
3. {HD04} Hammond T., Davis R.: Ladder, a sketching language for user interface developers. Elsevier, Computers and Graphics (2004), 35. 1
4. {HR07} Hou S., Ramani K.: Classifier combination for sketch-based 3d part retrieval. In Computers and Graphics (2007), vol. 31, pp. 598--609. 1
5. {HSN04} Hse H., Shilman M., Newton A. R.: Robust sketched symbol fragmentation using templates. In IUI'04: Proceedings of the 9th international conference on Intelligent user interfaces (2004), pp. 156--160. 2
6. {KK06} Kim D., Kim M.-J.: A curvature estimation for pen input segmentation in sketch-based modeling. In Computer-Aided Design (2006), vol. 38, pp. 238--248. 2
7. {KS05} Kara L., Stahovich T.: An image-based trainable symbol recognizer for sketch-based interfaces. In Computers and Graphics (2005), vol. 29, pp. 501--517. 1
8. {LJZ07} LaViola Jr. J. J., Zeleznik R. C.: A practical approach for writer-dependent symbol recognition using a writer-independent symbol recognizer. IEEE Trans. Pattern Anal. Mach. Intell. 29, 11 (2007), 1917--1926. 1
9. {LSC95} Lee J.-S., Sun Y.-N., Chen C.-H.: Multiscale corner detection by using wavelet transform. Image Processing, IEEE Transactions on 4 (1995), 100--104. 2
10. {LZ04} LaViola J., Zeleznik R.: Mathpad²: A system for the creation and exploration of mathematical sketches. ACM Transactions on Graphics 23, 3 (Aug. 2004), 432--440. (Proceedings of SIGGRAPH 2004). 1
11. {PH08} Paulson B., Hammond T.: Paleosketch: Accurate primitive sketch recognition and beautification. In IUI '08: Pro-ceedings of the 13th international conference on Intelligent user interfaces (2008), pp. 1--10. 1
12. {QWJ01} Qin S. F., Wright D. K., Jordanov I. N.: On-line segmentation of freehand sketches by knowledge-based non-linear thresholding operations. Pattern Recognition 34 (2001), 1885--1893. 1
13. {RC92} Rattarangsi A., Chin R.: Scale-based detection of corners of planar curves. Pattern Analysis and Machine Intelligence, IEEE Transactions on 14 (1992), 430--449. 2
14. {RW75} Rosenfeld A., Weszka J. S.: An improved method of angle detection on digital curves. IEEE Trans. Comput. 24, 9 (1975), 940--941. 2
15. {SD06} Sezgin T., Davis R.: Scale-space based feature point detection for digital ink. In SIGGRAPH '06: ACM SIGRRAPH 2006 Courses (New York, NY, USA, 2006), ACM, p. 29. 2
16. {SSD01} Sezgin T., Stahovich T., Davis R.: Sketch based interfaces: Early processing for sketch understanding. In Workshop on Perceptive User Interfaces (2001). 1, 2, 3, 5
17. {Sta04} Stahovich T.: Segmentation of pen strokes using pen speed. In Proceedings 2004 AAAI Fall Symposium on Making Pen-Based Interaction Intelligent and Natural (2004). 1
18. {TBP04} Thorne M., Burke D., Panne M.: Motion doodles: an interface for sketching character motion. In SIGGRAPH '04: ACM SIGGRAPH 2004 Papers (2004), pp. 424--431. 1
19. {TC89} Teh C., Chin R.: On the detection of dominant points on digital curves. IEEE Trans. Pattern Anal. Mach. Intell 17 (1989), 859--872. 2
20. {WEH08} Wolin A., Eoff B., Hammond T.: Shortstraw: A simple and effective corner finder for polylines. In EUROGRAPHICS 5th Annual Workshop on Sketch-Based Interfaces and Modeling (2008), pp. 33--40. 1, 2, 5, 6
21. {WWL04} Wobbrock J., Wilson A., Li Y.: Gestures without libraries, toolkits or training: a $1 recognizer for user interface prototypes. In Proceedings of the Nineteeth National Conference on Artificial Intelligence (AAAI-04) (San Jose, California, USA, 2004), pp. 159--168. 2
22. {Yu03} Yu B.: Recognition of freehand sketches using mean shift. In IUI '03: Proceedings of the 8th international conference on Intelligent user interfaces (2003), ACM, pp. 204--210. 2
23. {ZKS05} Zhai S., Kristensson P.-O., Smith B. A.: In search of effective text input interfaces for off the desktop computing. In Interacting with Computers (2005), vol. 17, pp. 229--250. 1

Index Terms

• Computing methodologies

  • Computer graphics

    • Image manipulation

    • Shape modeling

      • Parametric curve and surface models

• Human-centered computing

  • Human computer interaction (HCI)

    • Interaction paradigms

      • Graphical user interfaces