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 (2D-DP) 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.
Sketches are widely used in engineering and architecture fields, especially for the early design phases [1]. This is mainly due to the fact that a sketch is a convenient tool to catch rough ideas, so that the designers can focus more on the critical issues rather than on the intricate details [2]. The problem is that although it seems so quick and intuitive for humans to recognize sketches, it is really a great challenge for the computer [3].
A difficult task in sketch recognition is to have a good balance between the drawing freedom and the complexity of recognition. Generally, the more freely a system can endure, the more difficult sketch recognition will be. Consequently, for the sake of simplicity, most of the existing online recognition techniques are based on the assumption that people will not start to draw a new symbol before the current one has been finished. Obviously this is not always the case. One of the greatest advantages of sketch-based interface is that it provides a natural and free interaction platform. Therefore, it is a significant attempt to try solving the situation with interspersed symbols.
Like speech or text recognition, sketch recognition itself is domain dependent [3]. Domain knowledge to some extent can help recognition. Sketch recognition focuses on the localization and recognition of its constitutional components; the problem is that although isolated symbol recognition has been studied for many years, it still suffers in correctly rejecting outliers. Consequently, recognition based only on symbolic similarity is prone to errors. In this paper, we include contextual constraints to help to solve this problem. Here, constraints refer to the connectivity requirement of symbols, and we introduce a tolerant connectivity evaluation strategy.
This contribution is an extension of the work introduced in [4]. The dataset used for validating the proposed method has been extended from 10 to 15 subjects, with a total number of 130 sketches instead of 87. Furthermore, we have reformulated the problem statement and introduced the solution from a theoretical point of view. Additional experiments have also been conducted to assess the sustainability of a cost function combining pattern recognition information with soft contextual cost, which is a key point of the proposed framework.
The remainder of the paper is organized as follows. Section 2 provides a review of related works. Section 3 formulates sketch recognition as a dynamic programming problem. The details of our approach are presented in Section 4, followed by the experimental results in Section 5. Finally, conclusion and proposed future works are drawn in Section 6.
In this paper, sketch recognition task is formulated as a dynamic programming problem, and a circuit diagram recognition system is implemented based on this approach. As we introduced 2D-DP technique, our method can correctly locate interspersed symbols. Specifically, a tolerant connectivity function cost is introduced, which seems to be well suited to the task of recognizing free form sketches. With a point-level measurement, the experiment shows that the proposed novel approach is able to achieve an accuracy of more than 90 percent. This assessment is based on one hundred and thirty sketches featuring 10 different kinds of electrical symbols.
We are currently collecting samples from other application fields, so as to have a better understanding of when people would like to draw interspersed symbols. In our experiment, interspersing happened not only for the drawing of transistors, but also for the drawing of ac-voltages, currents, and dc-voltages. Observations suggest that people would like to draw the external circle first, then the connected connector, and strokes inside the circle at last. In such cases, people left a symbol obviously unfinished and returned later to finish it, which matches with the second drawing pattern underlying symbols drawn with non-consecutive strokes in [26]. This is not the same as has been discussed in [10], where people only draw transistors using interspersed symbols. We suggest that this is because, for one hand, there were only four components: resistors, capacitors, transistors and batteries in [10], and on another hand, in our experiment, participants were asked to copy diagrams according to the textbooks, whereas during the sample collection in [10], the textbook was removed. Whether or not interspersing happens more frequently in copying compared with in designing requires further study.
The DP approach has been proved to have a good potential to solve the sketch recognition problem, but the algorithm could be slow when the diagram is very large. Papadaki and Friderikos [27] have presented an approximate dynamic programming (ADP) methodology for large-scale problems. Hence how to develop a fast dynamic programming algorithm is another interesting topic for future study.
