Flexible Sequence Matching Technique: Application to Word Spotting in Degraded Documents

In this paper, a new sequence-matching algorithm, called as Flexible Sequence Matching (FSM) algorithm is proposed. FSM combines several abilities of other sequence matching algorithms (especially DTW, CDP and MVM) that could be configured depending on the application domain. Its generality and robustness comes from its ability to find subsequences (as in CDP), to skip outliers inside the match sequences (as in MVM) and to match multiple elements with a single one (as in CDP and DTW). These properties make it extremely suitable for robust word spotting. More precisely, the FSM algorithm has the capability to retrieve a query inside a line or piece of line. This facility is useful as word segmentation process may not work accurately or when only line segmentation information is available. Furthermore, thanks to its skipping capability, that makes the proposed FSM algorithm less sensible to local variations in the spelling of words, and also to local degradation effects. Finally, its multiple matching facilities (many to one and one to many matching) are useful in case of different length of target and query sequences due to the variability in scale factor. We demonstrate the superiority of proposed FSM algorithm in specific cases such as incorrect word segmentation and word level local variations. When different experiments were performed using handwritten George Washington dataset and also on historical typewritten document images, quite promising results were obtained.