Efficient graph-based dictionary search and its application to text-image searching

摘要

This paper describes a novel method for applying dictionary knowledge to optimally interpret the confidence-rated hypothesis sets produced by lower-level pattern classifiers. This problem arises whenever image or video databases need to be scanned for textual content, and where some of the text strings are expected to be strings from a dictionary. The method is especially appropriate for large dictionaries, as might occur in vehicle registration number recognition for example. The problem is cast as enumerating the paths in a graph in best-first order given the constraint that each complete path is a word in some specified dictionary. The solution described here is of particular interest due to its generality, flexibility and because the time to retrieve each path is independent of the size of the dictionary. Synthetic results are presented for searching dictionaries of up to l million UK postcodes given graphs that correspond to in- sertion, deletion and substitution errors. We also present the initial results from processing real noisy text images.