Full-Search-Equivalent Pattern Matching with Incremental Dissimilarity Approximations
Full-Search-Equivalent Pattern Matching with Incremental Dissimilarity Approximations
复制标题
具有增量相异近似的全搜索等效模式匹配
DOI：
10.1109/tpami.2008.46
复制
发表时间：
2009
影响因子：
23.6
通讯作者：
L. D. Stefano
中科院分区：
文献类型：
--
作者：
Federico Tombari;S. Mattoccia;L. D. Stefano
本文提出了一种基于从LP规范的差异函数（例如平方差（SSD）的总和）和绝对差异（SAD）的总和之和的新方法进行快速模式匹配的新方法。提出的方法是全面搜索等效的，即它与完整搜索（FS）算法相同的结果。为了追求计算储蓄，该方法部署了基于LP规范的差异函数的一系列越来越紧密的下限。这样的边界功能允许建立旨在快速跳过无法满足匹配标准的候选人的修剪条件的层次结构。本文包括提出的方法与文献中已知的其他全面搜索等效方法之间的实验比较，这证明了我们的建议的显着计算效率。
This paper proposes a novel method for fast pattern matching based on dissimilarity functions derived from the Lp norm, such as the Sum of Squared Differences (SSD) and the Sum of Absolute Differences (SAD). The proposed method is full-search equivalent, i.e. it yields the same results as the Full Search (FS) algorithm. In order to pursue computational savings the method deploys a succession of increasingly tighter lower bounds of the adopted Lp norm-based dissimilarity function. Such bounding functions allow for establishing a hierarchy of pruning conditions aimed at skipping rapidly those candidates that cannot satisfy the matching criterion. The paper includes an experimental comparison between the proposed method and other full-search equivalent approaches known in literature, which proves the remarkable computational efficiency of our proposal.