×
Feng, Guihuan; Viard-Gaudin, Christian; Sun, Zhengxing

On-line hand-drawn electric circuit diagram recognition using 2D dynamic programming. (English) Zbl 1186.68410

Pattern Recognition 42, No. 12, 3215-3223 (2009).
Summary: In order to facilitate sketch recognition, most online existing works assume that people will not start to draw a new symbol before the current one has been finished. We propose in this paper a method that relaxes this constraint. The proposed methodology relies on a two-dimensional dynamic programming technique allowing symbol hypothesis generation, which can correctly segment and recognize interspersed symbols. In addition, as discriminative classifiers usually have limited capability to reject outliers, some domain specific knowledge is included to circumvent those errors due to untrained patterns corresponding to erroneous segmentation hypotheses. With a point-level measurement, the experiment shows that the proposed novel approach is able to achieve an accuracy of more than 90 percent.

Cited in 2 Documents

MSC:

68T10 Pattern recognition, speech recognition
90C39 Dynamic programming

Keywords:

on-line sketch recognition; electric circuit diagram; dynamic programming

Software:

CALI
Cite Review PDF
Full Text: DOI HAL

References:

[1] Lipson, H.; Shpitalni, M., Conceptual design and analysis by sketching, Artif. Intell. Des. Manuf., 14, 5, 391-401 (2000)
[2] C. Calhoun, T.F. Stahovich, T. Kurtoglu, L.B. Kara, Recognizing multi-stroke symbols, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 15-23.; C. Calhoun, T.F. Stahovich, T. Kurtoglu, L.B. Kara, Recognizing multi-stroke symbols, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 15-23.
[3] Davis, R., Magic paper: sketch-understanding research, Computer, 40, 9, 34-41 (2007)
[4] G.-H. Feng, Z.-X. Sun, C. Viard-Gaudin, Hand-drawn electric circuit diagram understanding using 2D dynamic programming, in: Proceedings of the 11th International Conference on Frontiers in Handwriting Recognition, Québec, 2008, pp. 493-498.; G.-H. Feng, Z.-X. Sun, C. Viard-Gaudin, Hand-drawn electric circuit diagram understanding using 2D dynamic programming, in: Proceedings of the 11th International Conference on Frontiers in Handwriting Recognition, Québec, 2008, pp. 493-498.
[5] M.J. Fonseca, C. Pimentel, J.A. Jorge, Cali—an online scribble recognizer for calligraphic interfaces, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 51-58.; M.J. Fonseca, C. Pimentel, J.A. Jorge, Cali—an online scribble recognizer for calligraphic interfaces, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 51-58. · Zbl 1064.68620
[6] M. Liwicki, L. Knipping, Recognizing and simulating sketched logic circuits, in: Proceedings of the Ninth International Conference on Knowledge-based Intelligent Information and Engineering Systems, IOS Press, Melbourne, 2005, pp. 588-594.; M. Liwicki, L. Knipping, Recognizing and simulating sketched logic circuits, in: Proceedings of the Ninth International Conference on Knowledge-based Intelligent Information and Engineering Systems, IOS Press, Melbourne, 2005, pp. 588-594.
[7] Rubine, D., Specifying gestures by example, Comput. Graphics, 25, 4, 329-337 (1991)
[8] H. Hse, M. Shilman, A.R. Newton, Robust sketched symbol fragmentation using templates, in: Proceedings of International Conference on Intelligent User Interfaces (IUI), ACM Press, Funchal, 2004, pp. 156-160.; H. Hse, M. Shilman, A.R. Newton, Robust sketched symbol fragmentation using templates, in: Proceedings of International Conference on Intelligent User Interfaces (IUI), ACM Press, Funchal, 2004, pp. 156-160.
[9] Liu, W.-Y., On-line graphics recognition: state-of-the-art, (Lladós, J.; Kwon, Y. B., International Workshop on Graphics Recognition: Recent Advances and Perspectives, Lecture Notes in Computer Science, vol. 3088 (2003), Springer: Springer Barcelona), 289-302
[10] Sezgin, T. M.; Davis, R., Sketch interpretation using multiscale models of temporal patterns, Comput. Graphics Appl., 27, 1, 28-37 (2007)
[11] G. Costagliola, V. Deufemia, Visual language editors based on LR parsing techniques, in: Proceedings of the Eighth International Workshop on Parsing Technologies, Nancy, 2003, pp. 78-90.; G. Costagliola, V. Deufemia, Visual language editors based on LR parsing techniques, in: Proceedings of the Eighth International Workshop on Parsing Technologies, Nancy, 2003, pp. 78-90.
[12] L.B. Kara, T.F. Stahovich, Hierarchical parsing and recognition of hand-sketched diagrams, in: Proceedings of the 17th Annual ACM Symposium on User Interface Software and Technology (UIST2004), ACM Press, Santa Fe, 2004, pp. 13-22.; L.B. Kara, T.F. Stahovich, Hierarchical parsing and recognition of hand-sketched diagrams, in: Proceedings of the 17th Annual ACM Symposium on User Interface Software and Technology (UIST2004), ACM Press, Santa Fe, 2004, pp. 13-22.
[13] L.B. Kara, L. Gennari, T.F. Stahovich, A sketch-based interface for the design and analysis of simple vibratory mechanical systems, in: Proceedings of ASME International Design Engineering Technical Conference, Salt Lake City, 2004.; L.B. Kara, L. Gennari, T.F. Stahovich, A sketch-based interface for the design and analysis of simple vibratory mechanical systems, in: Proceedings of ASME International Design Engineering Technical Conference, Salt Lake City, 2004.
[14] Gennari, L. M.; Kara, L. B.; Stahovich, T. F.; Shimada, K., Combining geometry and domain knowledge to interpret hand-drawn diagrams, Comput. Graphics, 29, 547-562 (2005)
[15] C. Alvarado, R. Davis, Dynamically constructed bayes nets for multi-domain sketch understanding, in: Proceedings of the International Joint Conference on Artificial Intelligence, AAAI Press, Edinburgh, 2005, pp. 1407-1412.; C. Alvarado, R. Davis, Dynamically constructed bayes nets for multi-domain sketch understanding, in: Proceedings of the International Joint Conference on Artificial Intelligence, AAAI Press, Edinburgh, 2005, pp. 1407-1412.
[16] Sezgin, T. M.; David, R., Sketch recognition in interspersed drawings using time-based graphical models, Comput. Graphics, 32, 500-510 (2008)
[17] Hammond, T.; Davis, R., LADDER, a sketching language for user interface developers, Comput. Graphics, 28, 518-532 (2005)
[18] E. Saund, J. Mahoney, D. Fleet, D. Larner, E. Lank, Perceptual organization as a foundation for intelligent sketch editing, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 118-125.; E. Saund, J. Mahoney, D. Fleet, D. Larner, E. Lank, Perceptual organization as a foundation for intelligent sketch editing, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 118-125. · Zbl 1064.68624
[19] N. Zlatoff, B. Tellez, A. Baskurt, Image understanding and scene models: a generic framework integrating domain knowledge and gestalt theory, in: Proceedings of the International Conference on Image Processing, IEEE Press, Singapore, 2004, pp. 2355-2358.; N. Zlatoff, B. Tellez, A. Baskurt, Image understanding and scene models: a generic framework integrating domain knowledge and gestalt theory, in: Proceedings of the International Conference on Image Processing, IEEE Press, Singapore, 2004, pp. 2355-2358.
[20] Xie, L.-X.; Xu, P.; Chang, S.-F.; Divakaran, A.; Sun, H.-F., Structure analysis of soccer video with domain knowledge and hidden Markov models, Pattern Recognition Lett., 25, 767-775 (2004)
[21] I. Chaaban, Applying domain knowledge to the recognition of handwritten zip codes, Master Thesis, Indiana University South Bend, South Bend, 2005.; I. Chaaban, Applying domain knowledge to the recognition of handwritten zip codes, Master Thesis, Indiana University South Bend, South Bend, 2005.
[22] Held, M.; Karp, R. M., The construction of discrete dynamic programming algorithms, IBM Syst. J., 4, 2, 136-147 (1965)
[23] J. Hong, J. Landay, A.C. Long, J. Mankoff, Sketch recognizers from the end-user’s, the designer’s, and the programmer’s perspective, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 73-77.; J. Hong, J. Landay, A.C. Long, J. Mankoff, Sketch recognizers from the end-user’s, the designer’s, and the programmer’s perspective, in: Proceedings of AAAI Spring Symposium on Sketch Understanding, AAAI Press, Palo Alto, 2002, pp. 73-77.
[24] G.-H. Feng, HMM-based stroke fragmentation, Technical Report, Ecole Polytechnique de l’Université de Nantes, 2007 (available at ⟨http://hal.archives-ouvertes.fr/IRCCYN-IVC〉;).; G.-H. Feng, HMM-based stroke fragmentation, Technical Report, Ecole Polytechnique de l’Université de Nantes, 2007 (available at ⟨http://hal.archives-ouvertes.fr/IRCCYN-IVC〉;).
[25] T.Varga, H. Bunke, Generation of synthetic training data for an HMM-based handwriting recognition system, in: Proceedings of the Seventh International Conference on Document Analysis and Recognition, IEEE Computer Society Press, Edinburgh, 2003, 618pp.; T.Varga, H. Bunke, Generation of synthetic training data for an HMM-based handwriting recognition system, in: Proceedings of the Seventh International Conference on Document Analysis and Recognition, IEEE Computer Society Press, Edinburgh, 2003, 618pp.
[26] C. Alvarado, M. Lazzareschi, Properties of real-world digital logic diagrams, in: Proceedings of the First International Workshop on Pen-Based Learning Technologies, IEEE Computer Society Press, Catania, 2007, 12pp.; C. Alvarado, M. Lazzareschi, Properties of real-world digital logic diagrams, in: Proceedings of the First International Workshop on Pen-Based Learning Technologies, IEEE Computer Society Press, Catania, 2007, 12pp.
[27] Papadaki, K.; Friderikos, V., Approximate dynamic programming for link scheduling in wireless mesh network, Comput. Oper. Res., 35, 3848-3859 (2008) · Zbl 1278.90169
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.