Exemplary Sequence Cardinality: An effective application for word spotting

In this paper, a new sequence matching algorithm called as Exemplary Sequence Cardinality (ESC) is proposed. ESC combines several abilities of other sequence matching algorithms e.g. DTW, SSDTW, CDP, FSM, MVM, OSB¹. Depending on the application domain, ESC can be tuned to behave such as these different sequence matching algorithms. Its generality and robustness comes from its ability to find subsequences (as in CDP and SSDTW), to skip outliers inside the target sequences (as in MVM and FSM) and also in the query sequence (as in OSB ) and it has the ability to have many to one and one to many correspondences (as in DTW) between the elements of the query and the target sequences. It´s special characteristic of skipping noisy elements from query sequence along with other afore mentioned properties gives it an edge over FSM. In case of word spotting application, the outliers skipping capability of ESC makes it less sensible to local variations in the spelling of words, and also to noise present in the query and/or in the target word images. Due to it´s capability of sub-sequence matching, the ESC algorithm has the ability to retrieve a query inside a line or piece of line. Finally, its multiple matching facilities (many to one and one to many matching) is proven to be well advantageous in case of different length of target and query sequences due to the variability in scale, font, type/size factors. By experimenting on printed historical document images, we have demonstrated the interest of proposed ESC algorithm in specific cases when incorrect word segmentation and word level local variations occur regularly.