SEARCH ALGORITHMS FOR THE RECOGNITION OF CURSIVE PHRASES WITHOUT WORD SEGMENTATION

The paper addresses the problem of recognizing cursive phrases when word segmentation is very difficult or truly impossible, as in the case of literal amounts on Italian cheques, where words are written connected together. Since the general approach adopted for recognizing handwriting is that of generating a graph of segmentation hypotheses, the technical problem becomes that of searching for the path in the segmentation graph that matches optimally all the possible sequences of letters, represented also by paths in a graph that describes the phrase grammar.

The paper describes first the basic algorithm, discussing in particular the important issue of the form of the cost function in order not to bias recognition towards shorter phrases. Then we discuss a hierarchical decomposition of the search algorithm that fits with the usual hierarchical forms of linguistic knowledge representation, i.e. a grammar level and a lexical level. Accordingly, we describe a Hierarchical Dynamic Programming (HDP) algorithm, composed of a Sentence Level and a Word Level D.P. With a proper design, the HDP algorithm comes out very simple and WLDP results in a simple extension of the common search algorithms to recognize single words.