A fast search algorithm for template matching based on inequality criterion
A fast search algorithm for template matching based on inequality criterion
复制标题
一种基于不等式准则的模板匹配快速搜索算法
DOI：
10.1109/icosp.2004.1441542
复制
发表时间：
2004
期刊：
影响因子：
--
通讯作者：
Sun Guangfu
中科院分区：
文献类型：
--
作者：
W.A. Yang;Lu Huanzhang;Sun Guangfu
本文提出了一种模板匹配的快速搜索算法，该算法利用模板图像的平方误差失真度量与模板图像之和与每个可能匹配块之和的差值之间的不等性。首先对所有可能的匹配块和模板的和进行计算和排序。该算法利用不等性准则，剪枝候选匹配位置的个数。在计算块的和时，该算法利用相邻块的重叠来加快计算速度。由于不等式准则不依赖于任何假设，因此搜索结果与全搜索算法的结果等价。实验结果表明，与全搜索算法相比，该算法可以节省91.77%~93.25%的执行时间。
This paper presents a fast search algorithm for template matching, using the inequality between the square error distortion measure and the difference which is between the sum of template image and the sum of every possible matching block. Firstly the sums of all possible matching blocks and template are computed and sorted. Using the inequality criterion, the algorithm prunes the number of candidate matching positions. When computing the sums of blocks, the algorithm utilizes the overlapping of neighboring blocks to accelerate the calculation. Because the inequality criterion does not rely on any assumption, the search result is equivalent to the result of the full search algorithm. Experimental results show it can save 91.77% to 93.25% execution time comparing with full-search algorithm.