RECOVERING DRAWING ORDER OF SINGLE-STROKE HANDWRITTEN IMAGES USING PROBABILISTIC TABU SEARCH
Keywords:
Recovery drawing order, handwritten characters, graph theory, tabu searchAbstract
This paper considers the problem for recovering a drawing order of static handwritten images with single stroke. Such a stroke may include the so-called double-traced lines (D- lines). The problem is analyzed and solved by employing the graph theoretic approach. Then the central issue is to obtain the smoothest path of stroke from a graph model of input handwritten images. First, the graph model is constructed from an input images by image processing techniques. Then, we locally analyze the structure of graph. In particular, the method to identify D-lines is developed by introducing the idea of ‘D-line index’. The method enables us to transform any graphs with D-lines to semi-Eulerian graphs. Then, the restoration problem reduces to the problem of globally computing the maximum weight collection of perfect matchings. For solving such a problem, we propose a method using a probabilistic tabu search algorithm. The effectiveness and usefulness of the proposed method are examined by some experimental studies.
Downloads
References
S. Lee and J. C. Pan (1992), Offline Tracing and Representation of Signatures, IEEE Trans.
Systems, Man, and Cybernetics, Vol.22, No.4, pp.755–771.
T. Huang and M. Yasuhara (1995), Recovery of Information on the Drawing Order of Single-Stroke
Cursive Handwritten Characters from Their 2D Images, IPSJ Trans., Vol.36, No.9, pp.2132–2143.
S. J¨ager (1996), Recovering Writing Traces in Off-Line Handwriting Recognition: Using a Global
Optimization Technique, Proc. of 13th Int. Conf. on Pattern Recognition, pp.931–935, Vienna.
Y. Kato and M. Yasuhara (1999), Recovery of Drawing Order from Scanned Images of Multi-
Stroke Handwriting, Proc. of Fifth Int. Conf. on Document Analysis and Recognition, pp.261–264,
Bangalore, India.
Y. Kato and M. Yasuhara (2000), Recovery of Drawing Order from Single-Stroke Handwriting
Images, IEEE Trans. on Pattern Analysis and Machine Intelligence, Vol.22, No.9, pp.938–949.
H. Fujioka and T. Nagoya (2011), Recovering Stroke Order from Multi-Stroke Character Images,
Proc. of the 2011 2nd Int. Conf. on Innovative Computing and Communication, and 2011 2nd
Asia-Pacific Conference on Information Technology and Ocean Engineering, pp.34–37, Macao.
R. C. Gonzalez, R. E. Woods and S. L. Eddins (2009), Digital Image Processing Using MATLAB,
Prentice Hall.
J. R. Parker (2011), Algorithms for Image Processing and Computer Vision, Second Edition, Wiley
Publishing Inc.
Y. Qiao and M. Yasuhara (2004), Recovering Dynamic Information from Static Handwritten Im-
ages, Proc. of the Ninth Int. Workshop on Frontiers in Handwriting Recognition, Washington,
DC, USA.
A. Gibbons (1985), Algorithmic Graph Theory, Canbridge University Press.
D. Avis, A. Hertz and O. Marcotte (2005), Graphy Theory And Combinatorial Optimization , 3rd
edtition, Springer.
J. Edmonds B (1965), Paths, trees, and flowers, Canadian J. Math., Vol. 17, pp.449–467.
S. Micali and V. V. Vazirani (1980), An O(p|V ||E|) algoithm for finding maximum matching in
general graphs, Proc. 21st Annual Symposium on Foundations of Computer Science, Syracuse,
NY, USA.
Y. Wada and M. Kawato (2004), A via-point time optimization algorithm for complex sequential
trajectory formation, Neural Networks, Vol.17, No.3, pp.353–364.
