METHOD AND APPARATUS FOR DP MATCHING USING MULTIPLE TEMPLATES

A pattern recognition method and apparatus using dynamic programming in which an input sequence of labels is matched to a set of candidate templates (candidate reference label sequences). The set of candidate reference label sequences is grouped into subsets, where each reference label sequence in a subset has a common root reference label subsequence. Using this set organization, a depth-first search is performed to identify a local optimum template and its local optimum match score with the input sequence of labels. Using the local optimum match score as a threshold, the input sequence of labels is matched to root reference label subsequences, eliminating those root reference label subsequences having match scores above the threshold. Surviving root reference label subsequences having match scores below the threshold remain recognition candidates, and are further investigated.