| This paper presents an investigation of a cognitive problem in terms of complexity theory. Two global optimization approaches are presented for recovering trajectories from static, handwritten word images. Both take graph-theoretical representations of symbols as input. The first, polynomial approach minimizes the length of the recovered trajectories. This approach cannot recover trajectories traversing parts of the word more than twice. The second approach, which minimizes costs at distinguished nodes of the trajectory, is more powerful in this respect and is proved to be NP-hard. An eÆcient divide-and-conquer method is proposed that splits handwritten words into independent subparts and recovers trajectories for every subpart, which turn out to be very small in practice. The splitting technique exploits morphological features from the static word image. pp. 291-302. |
In: L.R.B. Schomaker and L.G. Vuurpijl (Eds.)
Proceedings of the Seventh International Workshop on Frontiers
in Handwriting Recognition, September 11-13 2000, Amsterdam,
Nijmegen: International Unipen Foundation,
ISBN 90-76942-01-3