渐进不相似度逼近(IDA)算法是一种新近提出的高性能快速图像匹配算法,它通过分割匹配矢量,避免了大量的基于像素的计算。但是分割后的子矢量能量集中性差,因此算法效率仍有提升空间。为了改进能量集中性差这个问题,提出一种按子矢量方差顺序展开的方案,按该顺序展开子矢量能使匹配矢量排除得更快,平均展开的子矢量数下降,明显减少了搜索空间。除此之外,还加入了在IDA测试之前的利用整体矢量模的一次新的排除测试,并在子矢量展开中引入了PDS(partial distortion search)算法。本文改进算法对图像数据库中室内场景、室外自然场景和室外人文场景这3类图像进行测试时,整体匹配效率较IDA算法提升了72%~83%。

The incremental dissimilarity approximations (IDA) algorithm is a recently proposed high-efficient fast image pattern matching algorithm. By splitting the matching vectors, the IDA algorithm saves a lot of pixel-dependment calculations. However,the sub-vectors have a rather weak energy compaction after splitting. This means IDA’s efficiency can further be improved. To avoid the weak energy compaction, sub-vector ordering is proposed, which sorts the sub-vectors by their variances. Candidates would be pruned earlier by the sorted order in pattern matching. Therefore, the average number of unfolded sub-vectors is reduced, which also reducts the search space. Additionally,one more pruning test using the whole vector’s norm before IDA is proposed in our work, and the PDS (partial distortion search) algorithm is introduced in the unfolding sub-vectors step. In our experiment, by testing three types of images in the data sets(indoor scene, natural scene, streetscape), the overall efficiency of proposed algorithm is improved by 72%~83% compared to the original IDA algorithm.