子矢量排序的渐进不相似度逼近算法

Improved incremental dissimilarity approximations algorithm using sub-vector sorting

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

The incremental dissimilarity approximations （IDA） algorithm is a recently proposed high-efficient fast image pat- tern 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 vari- ances. 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.