An efficient algorithm for matching a lexicon with a segmentation graph

Abstract

This paper presents an efficient algorithm for lexicon-driven handwritten word recognition. In this algorithm, a word image is represented by a segmentation graph, and the lexicon is represented by a trie. As opposed to the standard lexicon-driven matching approach, where dynamic programming is invoked independently for matching each entry in the lexicon against the segmentation graph, the proposed algorithm matches the trie with the segmentation graph. Computation is saved by the efficient representation of the lexicon using the trie data structure. The performance of the proposed approach is compared with the standard dynamic programming algorithm. The proposed approach saves about 48.4% (excluding the trie initialization cost) and 15% of computation time from the standard algorithm when a dynamic lexicon is used. Better performance can be expected in static lexicon cases where the trie needs to be constructed only once.