access icon free Online stroke segmentation by quick penalty-based dynamic programming

A stroke segmentation method named quick penalty-based dynamic programming is proposed for splitting a sketchy stroke into several regular primitive shapes, such as line segments and elliptical arcs. The authors extend the dynamic programming framework with a customisable penalty function, which measures the correctness of splitting a stroke at a particular point. With the help of the penalty function, the proposed dynamic programming framework can finish the stroke segmentation process without any prior knowledge of the number and/or the type of segments contained in the sketchy stroke. Its response time is sufficiently short for online applications, even for long strokes. Experiments show that the proposed method is robust for strokes with arbitrary shape and size.

Inspec keywords: computational geometry; dynamic programming; image segmentation

Other keywords: sketchy stroke; online stroke segmentation; line segments; regular primitive shapes; dynamic programming framework; stroke segmentation process; online applications; customisable penalty function; elliptical arcs; penalty-based dynamic progacramming

Subjects: Optimisation techniques; Graphics techniques; Optimisation techniques; Computer vision and image processing techniques; Optical, image and video signal processing; Computational geometry

References

    1. 1)
      • 3. Wenyin, L., Kong, X., Wang, Y., et al: ‘QuickDiagram: a system for online sketching and understanding of diagrams’, in: Ogier, J.-M., Liu, W., Lladós, J. (eds.), Graphics recognition. achievements, challenges, and evolution (Springer, Berlin/Heidelberg) (LNCS6020), 2010, pp. 130141.
    2. 2)
      • 21. Fitzgibbon, M.P., Fisher, R.B.: ‘Direct least square fitting of ellipses’, IEEE Trans. Pattern Anal. Mach. Intell., 1999, 21 pp. 476480 (doi: 10.1109/34.765658).
    3. 3)
      • 12. Brault, J.J., Plamondon, R.: ‘Segmenting handwritten signatures at their perceptually important points’, IEEE Trans. Pattern Anal. Mach. Intell., 1993, 15, (9), pp. 953957 (doi: 10.1109/34.232079).
    4. 4)
      • 13. Teh, C.H., Chin, R.T.: ‘On the detection of dominant points on digital curves’, IEEE Trans. Pattern Anal. Mach. Intell., 1989, 11, (8), pp. 859872 (doi: 10.1109/34.31447).
    5. 5)
      • 6. Yang, Z., Guangshun, S., Kai, W.: ‘A SVM-HMM based online classifier for handwritten chemical symbols’. 20th Int. Conf. on Pattern Recognition, 2010, pp. 18881891.
    6. 6)
      • 3. Wenyin, L., Kong, X., Wang, Y., et al: ‘QuickDiagram: a system for online sketching and understanding of diagrams’, in: Ogier, J.-M., Liu, W., Lladós, J. (eds.), Graphics recognition. achievements, challenges, and evolution (Springer, Berlin/Heidelberg) (LNCS6020), 2010, pp. 130141.
    7. 7)
      • 18. Horng, J.H., Li, J.T.: ‘A dynamic programming approach for fitting digital planar curves with line segments and circular arcs’, Pattern Recognit. Lett., 2001, 22, pp. 183197 (doi: 10.1016/S0167-8655(00)00104-5).
    8. 8)
      • 2. Zhu, B., Iwata, M., Haraguchi, R., et al: ‘Sketch-based dynamic illustration of fluid systems’, ACM Trans. Graph., 2011, 30, (6), pp. 18 (doi: 10.1145/2070781.2024168).
    9. 9)
      • 17. Feng, G., Viard-Gaudin, C., Sun, Z.: ‘On-line hand-drawn electric circuit diagram recognition using 2D dynamic programming’, Pattern Recognit., 2009, 42, (12), pp. 32153223 (doi: 10.1016/j.patcog.2009.01.031).
    10. 10)
      • 10. Rosenfeld, A., Johnston, E.: ‘Angle detection on digital curves’, IEEE Trans. Comput., 1973, 22, pp. 875878 (doi: 10.1109/TC.1973.5009188).
    11. 11)
      • 9. Liu, Y., Yu, Y.J., Liu, W.Y.: ‘Online segmentation of freehand stroke by dynamic programming’. Proc. ICDAR, 2005, pp. 197201.
    12. 12)
      • 4. Dachselt, R., Frisch, M., Decker, E.: ‘Enhancing UML sketch tools with digital pens and paper’. Proc. Fourth ACM Symp. on Software Visualization, 2008, pp. 203204.
    13. 13)
      • 16. Noris, G., Sýkora, D., Shamir, A., et al: ‘Smart scribbles for sketch segmentation’, Comput. Graph. Forum, 2012, 31, pp. 25162527 (doi: 10.1111/j.1467-8659.2012.03224.x).
    14. 14)
      • 7. Olsen, L., Samavati, F., Sousa, M., Jorge, J.: ‘Sketch-based modeling: survey’, Comput. Graph., 2009, 33, pp. 85103 (doi: 10.1016/j.cag.2008.09.013).
    15. 15)
      • 20. Hse, H., Shilman, M., Newton, A.R.: ‘Robust sketched symbol fragmentation using templates’. Int. Conf. Intelligent User Interface, Madeira, Portugal, 2004.
    16. 16)
      • 19. Tümen, R., Sezgin, M.: ‘DPFrag: a trainable stroke fragmentation framework based on dynamic programming’, IEEE Comput. Graph. Appl., DOI: 10.1109/MCG.2012.124.
    17. 17)
      • 11. Rosenfeld, M.T., Lee, Y.H.: ‘Edge and curve detection: further experiments’, IEEE Trans. Comput., 1972, 21, pp. 677715 (doi: 10.1109/T-C.1972.223573).
    18. 18)
      • 14. Ray, B.K., Pandyan, R.: ‘ACORD – an adaptive corner detector for planar curves’, Pattern Recognit., 2003, 36, pp. 703708 (doi: 10.1016/S0031-3203(02)00084-5).
    19. 19)
      • 1. Alvarado, C., Davis, R.: ‘SketchREAD: a multi-domain sketch recognition engine’. ACM SIGGRAPH 2007 Courses: 34, 2007.
    20. 20)
      • 15. Herold, J., Stahovich, T.F.: ‘SpeedSeg: a technique for segmenting pen strokes using pen speed’, Comput. Graph., 2011, 35, (2), pp. 250264 (doi: 10.1016/j.cag.2010.12.003).
    21. 21)
      • 5. Shah, D., Schneider, J., Campbell, M.: ‘A robust sketch interface for natural robot control’. IEEE/RSJ Int. Conf. on Intelligent Robots and Systems, 2010, pp. 44584463.
    22. 22)
      • 8. Kim, D.H., Kim, M.-J.: ‘A curvature estimation for pen input segmentation: in sketch-based modeling’, Comput.-Aided Des., 2006, 38, pp. 238248 (doi: 10.1016/j.cad.2005.10.006).
http://iet.metastore.ingenta.com/content/journals/10.1049/iet-cvi.2012.0296
Loading

Related content

content/journals/10.1049/iet-cvi.2012.0296
pub_keyword,iet_inspecKeyword,pub_concept
6
6
Loading