经典图像快速匹配算法比较分析研究

王 坚

(辽宁对外经贸学院，辽宁 大连 116000)

图像匹配即是应用某种特殊的逻辑运算和数学方法在两幅图片之间寻找共同点[1]。图像匹配的研究工作很早就在国外开始了，70年代的美国为了军事的需要开启了关于图像匹配的研究工作，主要是针对武器的飞行导航功能[2]。我国研究起步虽然比较晚，但是也有不少新的突破。其一，是图像匹配过程中特征提取算法的改进，包括SIFT检测算法、CNN算法、KNN算法和AKAZE算法等。其二，是联合算法的设计与实现，例如多尺度PCA-HOG联合技术提高算法的运行速度[3]；KNN与RANSAC相结合改变抽样规格与匹配模式，提高算法的鲁棒性[4]。其三，是快速匹配算法的开发，例如基于改进SURF的快速匹配算法，与传统算法相比提高30%的运行效率[5]。本文以灰度图像为研究对象，分别比较常用的灰度图像匹配的算法、改进的灰度图像匹配的算法(序贯相似性算法)和局部灰度编码算法在图像快速匹配中的性能，为图像匹配算法的开发提供理论基础。

1 数字图像匹配技术概述

1.1 基于模板法的图像匹配方法

模板匹配是指通过尺寸更小的图像模板与源图像进行比较分析。想要确定模板是否与源图像有相同或相似的区，则需要求出相似区域的位置和坐标，然后提取图像。模板匹配的步骤如图1所示。基于模板法的图像匹配算法有许多，比较常见的主要包括误差平方和算法(SSD)和基于误差平方和的序贯相似性检测算法(SSDA)。

图1 模板算法流程图

1.1.1 误差平方和算法(SSD)[6]

误差平方和算法主要是通过求解模板图像与源图像相似区域的误差平和进行图像的匹配。假设f(x,y)为M×N的源图像，t(j,k)为J×K(J≤M,K≤N)的模板图像，则误差平方和测度定义为：

(1)

由上式展开可得：

(2)

(3)

(4)

(5)

其中，DS(x,y)称为源图像中与模板对应区域的能量，其大小与像素的位置有关。DST(x,y)为模板与源图像对应区域的互相关性。DT(x,y)为模板的能量。

1.1.2 基于误差平方和的序贯相似性检测算法(SSDA)

序贯相似性检测算法是对传统模板匹配算法的改进，增加了阈值参数。SSDA算法定义绝对误差[7]：

(6)

其中，带有上划线的分别表示子图、模板的均值：

(7)

(8)

实际上，绝对误差就是子图与模板图各自去掉其均值后，对应位置差的绝对值，然后设定阈值Th；在模板图中随机选取不重复的像素点，计算与当前子图的绝对误差，将误差累加，当误差累加值超过了Th时，记下累加次数H，所有子图的累加次数H用一个表R(i,j)来表示。SSDA检测定义为：

(9)

1.2 基于改进的模板图像匹配快速算法

整个图像被划分成k×k处的大小和非重叠正方形中，然后对图像进行分块，如果我们把图像分割以后剩下的部分数量不是k的倍数，则底部和剩余行的最右边、列切割。R-块中，R，S(Ri)的R-块表示像素Ri的灰度值和。块R-附近的组成(图2b)，D-Block的定义和其周围的八个块相邻的R(图2a：R1，R2，R3，R4，R6，R7，R8，R9示出)；将R-块的邻域分为4个部分，分别为D1，D2，D3，D4(如图2b)，称为R-块的D-邻域；R-块R5分别属于4个D邻域，即D1=R1∪R2∪R4∪R5；D2=R4∪R5∪R7∪R8；D3=R5∪R6∪R8∪R9；D4=R2∪R3∪R5∪R6。

图2 图像划分

对每一个D-R-附近的四大模块，需要一个序列(图2的逆时针顺序)像素对Dj灰度总值进行表示。包括：S(Rj1)、S(Rj2)、S(Rj3)、S(Rj4)共有24(4!)种可能；可以用五位二进制代码来表示。称作P(Dj)∈{00000，00001，L10111}来表示。这样的24种就是所谓的对应的位置关系，它们有24种，如果采取对D块内扭转(逆序)R-4块。其中每个对应于灰度排序之间的位置关系，我们可以进行编码再固定，当然，我们也可以使用序列。将R-块Ri所在的4个D-块的P(Dj)做位串并接得到：F(Ri)=P(D1)P(D2)P(D3)P(D4)，接着对4个(Dj)具体操作是：F(Ri)=(P(D1)<<15)+(P(D2)<<10)+(P(D3)<<5)+P(D4)。其中P(Dj)是Rj邻域Dj的二进制码，后面的数字表示移位。2F(Ri)是块20的二进制编码的表示，称为块编码。通过上述简单的推论可以得知，Ri编码块的类型可有244种，但是F(Ri)表示位置的关系应该在相邻的八领域块的灰度和(R-块Rj之间)排布。当D1中块之间的位置关系被确定，以及灰度值总值被确后，D2和D4块之间的关系(总值灰度)就不可能24种，是12种。R4和R5再加上R2和R5俩对关系已经很明显的，所以D3只有六个可能的种类，虽然我们做了这么多的简化推论，看起来少了不少种类，但是仍然要计算至少24*12*12*6=20736种，导致了计算量仍然不小，因此在计算整幅图像的时候出现的重码的概率应该是非常低的，这也是种方法的准确性的体现。此外，该编码方法反映了灰度图像的灰度相对值。所以，相对稳定的灰度值也使得计算少了许多干扰，抗噪声能力很强。用k的选择粒度的大小可以改变图像处理的大小，方便在不同的噪声情况下对象图像进行处理。

用搜索图S搜索以模板T的长度、宽度水平、垂直步长为标准。从左上方以T的大小分割至S称为限制块C(i，j))。由它开始，其中(i，j)为限制块左上角顶点在搜索图S上的坐标。这种划分之后，如果我们还可以在右侧或底部搜索到S的没有被覆盖的部分，那么我们就可以从相应起始位置的最右侧向S的左侧搜索，或从底部开始重新划分成块或限制线，使得全部限制块可以完全覆盖搜索图S。限制块C(i，j))和T是N×N模板图像的尺寸，其中，每个组可用块R-矩阵A(C(i，j))与A(T)表示已知特征编码矩阵，其中K是一个侧R-块的边长。比较A(C(i，j))和A(T)的每个元素相同的行号列号，记录行列号。和分形编码检索中遇到的问题一样，也是在两图中很显然的问题，就是说怎么对准R-块。我们来看(图3a)是模板图的阴影部分和搜索图和图S的模板T匹配。然而，在对模板T和搜索图S进行块R分割后，就没有两者之间的相同的R-块了，这是R-块就不能很好的表示两幅图像的局部相似度了，匹配率将受到不同程度的影响。因此，有必要对模板T做合适的剪切，在图中移除阴影部分。如(图3b)，剩余的子区域可被配置为如图3c中，然后图3b中的右下侧4个R块对齐。

图3 S搜索示意图

在为了实现图R-块对齐的模板T和S中的特征匹配，模板T可正确切割，在模板图T的行x、列y被切割(0

ph，j.right=Dright+k

(10)

ph，j.left=Dleft-Tx，y-D.width-k

(11)

其中左，右，宽度，分别是矩形的左和右边缘坐标和宽度。由以上可以得出我们在进行局部灰度编码算法匹配时候的步骤为：对样本模板T与做K2次剪切，并计算T(x，y)的特性；计算出基于搜索图S所有的R-块的特征；以C(i，j))确定搜索图S大小(图S的最右面或最低部有很大的可能被限制快重影)；对于每块限制C(i，j))的模块，包含在R块排序的特征编码矩阵A(C(i，j))，再对模板T的K2剪切后的有序特征集做有序比较。发现限制块C(i，j))与裁剪模板T(x，y)的最相似的特性；重新有序比较对C(i，j))与模板T(x，y)的特征值。用两个一维数组linecolL来表示累计矩阵A(C(i，j))各行、列的特征比较结果；求得限制块C(i，j))内匹配子区域D的边界，需要对linecolL数组做边缘检测滤波；求出模板T在搜索图S中匹配的参考点。由D与限制块C(i，j))的相对位置关系与裁剪情况T(x，y)得出。

2 结果分析

2.1 图像匹配结果

以网络上下载的辽宁对外经贸学院的正门图像(简称“ZM”)做为实验对象。第一步，输入源图像读出两个图像ZM1和ZM0，如图4。以这两个图像为匹配的模板。

图4 从Matlab中提取目标文件

第二步：选取ZM0/ZM1中的各一个区域，定义新的名称。(选取的图像区域要事先选定好，不能太过偏离图像特征区域，以免实验的匹配效果不佳)显示选中的区域图像。第三步，在两幅图像中进行归一化互相关计算。就是比较匹配图像和待匹配图像之间的互相关点，然后确定互相关点的峰值；最后确定待匹配图像在匹配图像的位置，但该计算能更直接的显示图像特征点。通过Matlab软件显示一个三维的峰值图像，找到图像最佳匹配点，特征点结果如图5所示。

图5 相似度比较峰值-特征点 图6 图像匹配结果

第四步，确定图像最大匹配点，继续进行图像的线性预算，为后续的图像匹配做准备。第五步，继续为最后的图像匹配做准备。在图像内提取区域，找出区域属于源图像的哪部分，提取出区域和原图像进行比较。第六步，为防止图像匹配中可能出现图像的不规则，图像倾斜或者畸变，导致进行图像匹配时间延迟。先定义一个零矩阵，把图像定义在一个黑色的背景下，方便图像的匹配，使图像在匹配中可以以点的形式一点点匹配，防止图像在匹配后出现的畸变，省去匹配后的校正过程。第七步，先是图像的灰度处理，然后设计结果显示。把彩色图像匹配到灰色图像中，结果如图6所示。

2.2 耗时性比较分析结果

误差平方和算法的优点，计算简单，易学易用；缺点是计算量比较大，需要的时间比较久。不满足匹配快速的要求，而且匹配原理简单，容易受到外界噪声的干扰。序贯相似性算法的优点，各步骤的计算量要比误差平方和快2-3倍；缺点是时间复杂度高，对搜索图尺寸要求比较高。总的来说这两种算法仅是基于灰度信息的相似性来比较差值，需要比较大量的像素点，所以计算量还是比较大的，达不到快速匹配的目的。而局部灰度编码算法把要匹配的图像划分割成若干块，然后计算每块的灰度值，接着把整个图像的局部灰度值按照顺序划分排序，进行编码。最后和模板图像进行比较，实现图像的匹配。由于把图像从空间上的层次转换到编码的层次，所以它的计算量有了很大的缩减，速度有极大的提高(见表1)。所以说局部灰度编码算法还是可以达快速匹配(计算量小、匹配时间短、匹配精确)的要求。为了比较经典的图像匹配算法与深度学习算法的耗时性能，选取了鲁棒性较好的基于学习的不变特征变换算法(LIFT)[8]进行图像匹配分析。LIFT算法采用了一种改进的SIFT图像特征点提取技术，通过Kd-Tree特征结构、BBF搜索策略和HOUGH聚类进行图像匹配，完成图像匹配耗时为1324.210ms。

表1 各个算法运行时间记录(ms)

3 结论

图像匹配将计算机视觉、多维信号处理和数值计算紧密联合形成了密切相关的近领域交叉技术。本文所使用的灰度图像匹配方法的基础是图像的相似度，即灰度信息所代表的灰度值的大小之间的关系。寻找块匹配灰色信息区域的相似度的大小，可以用波形的峰值确定最大相似度区域以提高搜索的效率和准确性。通过测试发现，传统的模板匹配算法和序贯相似性算法具有较好的鲁棒性，而序贯相似性所要的时间要比传统的模板匹配算法少得多。传统的模板匹配算法的主要时间都用在匹配图像和模板图像之间的平滑过程，序贯相似性算法则首先设定了阈值，阈值越是接近相似度最高点，匹配的时间越短，精确度也越高。而基于学习的不变特征变换算法(LIFT)尽管具有较好的鲁棒性[11]，但复杂的运算过程增加了图像匹配的耗时。所以，相对于一般传统的模板匹配算法而言，序贯相似性已经可以实现图像的快速匹配的要求。