Linear scaling based dynamic programming algorithm for accurate matching in QBH

A linear scaling (LS) based dynamic programming (DP) algorithm was developed for accurate matching of queries by humming. The query contours are split into phrases, with the LS match calculated for each phrase. Finally dynamic programming is used to analyze on all the phrases to choose the optimal matching path. The algorithm more efficiently considers the query contours related to the phrases, thus, overcoming the missing-global-optimal-path disadvantage of dynamic programming for long path matching. Tests on a 5 223 MIDI database show that the algorithm outperforms the traditional LS method by 10.5%, the DP method by 6.0% and recursive alignment by 2.8% for the top-1 rate. Thus, the algorithm is more efficient and more accurate while being less expense.