基于变换矩阵空间优化搜索的模板匹配方法

基于变换矩阵空间优化搜索的模板匹配方法

1基于模板匹配的目标检测算法基于视觉检测目标，如人类检测、行人检测、车辆检测等。通常需要通过算法学习获取模型模型和分类器模型的参数，然后利用模型和分类器模型确定实时目标的参数。传统机器学习的方法做目标检测达到较高水平的如梯度方向直方图特征(HistogramofOrientedGradient,HOG)结合支持向量机(SupportVectorMachine,SVM)分类器基于模板匹配的目标检测只需要具有目标模板图像,通过匹配算法找到实时图像中与目标模板图像相似的区域位置,达到检测模板目标的目的。当前已有较多学者研究了基于模板匹配的目标检测算法航空图像处理领域中,由于航空拍摄距离较远,拍摄角度变化差异较大,通常图像场景较复杂,目标较小,分辨率远低于通常意义下拍摄的图像(如照相机、手机、监控摄像头等拍摄的图像),因此制作的目标模板较小,低分辨率下图像特征较弱,复杂场景带来的干扰较大,多视角拍摄造成模板图像与实时图像之间的空间变换关系复杂,特殊的拍摄场景与方式给航空图像的模板匹配方法带来了许多待解决的难点,总结主要有以下几点:(1)多视角问题。多视角造成制备的目标模板图像与实时图像间的视角差异大、种类多,图像之间的空间变换关系复杂,基于灰度匹配的方法无法解决多视角问题。(2)小目标弱特征问题。小目标本身模板图像小,能够提取的特征较少,采用局部特征点的匹配方法容易失败。(3)航空平台由于载荷有限,计算资源有限,航空图像通常数据量较大,对算法的高效性有特殊的要求。本文针对上述问题,结合航空图像的特点,提出一种多视角自适应的模板匹配方法。通过分解多视角下图像之间的空间变换关系,构建空间变换矩阵的搜索空间,然后在整个搜索空间中通过优化搜索的方法寻找到全局最优的空间变换关系。考虑到小图像弱特征的问题,不采用难以提取的局部点特征,而将优化搜索的目标函数定义为模板图像与实时图像归一化灰度的函数,从而充分利用所有的图像信息。2模型匹配模型2.1模型匹配问题的建模假设模板图像为若模板图像在实时图像中能找到匹配区域,则模板图像I模板图像I定义模板图像I如果p2.2单元网格线划分解决优化问题(4)必须定义优化搜索的矩阵空间。矩阵空间由所有可能的变换矩阵组成,将变换矩阵分解成如下三个部分:式中:等式右边第一项是仿射变换,包含了平移、旋转等刚体变换和缩放等相似变换;第二项和第三项是纯透视变换,分别在x方向和y方向透视投影。将其中仿射变换进行QR分解,得到旋转、平移和缩放三种变换为其中平移变换包含x方向和y方向上的平移,共两个自由度,旋转变换R缩放变换S包含x方向上的缩放和y方向上的缩放,共两个自由度加上x和y方向上的透视变换共2个自由度,变换矩阵H具有8个自由度,因此,矩阵空间Φ有8个维度,即Φ∈R通过计算发现,变换矩阵Δ如图3所示,若定义模板图像I式中:‖·‖如果将矩阵空间Φ离散化,即将每一个维度按一定的间隔进行网格划分,共8个维度的划分组成一个离散的网格,若网格划分的精度为δ(0<δ<1),记为N按照表1划分矩阵空间Φ,每一个网格线的交点即为一个矩阵变换,所有的矩阵变换H如图4所示,如果网格的划分间隔为δ,根据文献[13]可以证明,对于Φ中的任意一个变换H∈Φ,N式中:Ο(·)表示等式左边的渐近上界与括号中的表达式存在常数倍关系。因此,给定一个误差精度δ>0,在矩阵空间N于是优化问题(4)可以在离散空间求的近似解,即3时间复杂度在网格N输入:归一化的灰度图像I输出:ΔStep1在图像IStep2计算并返回Δ显然,算法1的时间复杂度为Ο(1/δ输入:归一化的灰度图像I输出:变换矩阵HStep1创建网格NStep2若i≤N,对HStep3若ΔStep4i=i+1,返回Step2,直至循环结束。Step5返回H4快速匹配检测利用算法2进行最优变换矩阵的求解,其计算的时间复杂度为N=Θ((1/δ分支界限法的思想是先用低精度的网格去划分空间,快速找到最优解的区域界限,然后在最优解区域内再进行高精度网格划分,进一步找到最优解的更精确界限,重复上述步骤将最优解界限不断缩小,直至逼近至最优解。分支界限法要避免的是陷于局部最优,如果在低精度网格中找到的最优解界限中不包含全局最优解,由于后面的处理分支均是在当前最优解界限中寻找更逼近的界限,所以后面找到的最优解一定不是全局最优。为了直观地描述这个问题,如图5所示,我们在一维空间进行网格划分查找最优界限,其中横轴矩阵空间Φ,间隔相等的灰色竖线是以精度δ对空间Φ进行划分的网格N由于SAD随着H的变化是平滑的,根据式(13)有Δ多目标匹配检测问题中,一个模板可能与实时图像中多个区域匹配,故应该返回多个变换矩阵H传统模板匹配方法分为两种,基于灰度的模板匹配方法只能解决平移变换,快速傅里叶方法能解决一定程度的旋转变换;基于特征的模板匹配方法是通过特征匹配后寻找两幅图像之间的同名控制点,然后直接求得变换矩阵的闭式解。但是,当模板图像中有效特征较少,如弱纹理图像、实时图像中干扰特征较多、图像之间视角差异较大等情况,特征描述子的旋转、缩放、仿射不变性能力有限,特征匹配的成功率通常非常低,可能无法得到闭式解或者闭式解的误差较大。本文从优化搜索的思路出发,分析3×3的图像变换矩阵,发现原始变换空间拥有8个自由度,每个自由度的取值都是连续的,即其取值集合有无穷维,无法通过优化搜索的方法得到最优的变换矩阵,那么考虑在一定的精度下降连续的变换空间进行离散化数学建模,进而在离散化的变换空间完成最优矩阵的搜索。5实验和结论5.1匹配的投影误差测试为了测试本文方法的效果,利用VOC2010dataset为了测试算法对投影变换的鲁棒性,将模板图像进行90%、70%、50%、30%、10%的5种比例的缩放,然后进行测试。测试中定义匹配的投影误差为式中:C为了测试算法的抗噪声性能,对250个样本中的每一个样本按表3所示三种方式进行退化处理,生成更多的测试样本。在上述测试集上将本文模板匹配算法与当前最稳定的SIFT特征匹配算法如图7所示,横坐标表示图像经过6种不同级别的退化处理,纵坐标表示匹配成功的概率(总共220个测试样本)。5.2匹配检测结果经典的模板匹配算法如SAD、MAD、均方误差、SSD、NCC、信息熵等基于灰度的匹配算法只能解决模板与实时图像之间的平移关系,在频域中处理可以解决一定程度的旋转变换,但无法解决仿射变换、投影变换、由于测试图像对之间存在仿射投影变换,因此这里无法参与测试比较。基于特征的匹配算法有SIFT如图8所示,分别使用了实际采集的航空图像和标准库中的图像进行测试,每一行是一个测试样例,每行的第一列是模板图像,第二列和第三列分别是本文的匹配检测结果和SIFT匹配检测结果。其中第一行为机场中飞机目标检测样例,模板图像的分辨率较低;第二行为训练场中车辆目标检测样例,目标模板相对场景图像的旋转角度较大;第三行是标准库中的图像匹配样例,模板图像相对场景图像的仿射变换较大;第四行和第五行是港口舰船检测样例,模板图像有一定的旋转且分辨率较低。其中第一行和第二行均是单模板多目标匹配检测问题。分别使用本文方法和SIFT匹配方法测试上述样例,其中本文算法参数设置为缩放尺度范围s=10,平移范围c为实时图像的尺寸,网络精度为0.01,阈值为0.1。SIFT算法采用公开库VLFEAT本文算法与SIFT、ORB算法的运行时间比较如表4所示,其中“NaN”表示匹配失败。由实验结果可见,SIFT算法匹配时间较长,ORB算法稳定性能较差,本文算法采用暴力搜索算法遍历整个变换空间,其时间消耗比传统的SIFT算法还大长,经过分支界限法加速后,速度可以显著提高。这是因为分支界限法首先在粗粒度的网格划分下找到最优解的可行区域(分支),迅速排除掉其他分支,从而大大减少无效计算,然后在找到的可行分支再进行细粒度网格划分,进而找到精度更高的最优解的可行分支,这样通过不断缩小最优解的可行范围避免无效运算,在满足精度要求下可以接受当前的最优可行解。6大差异视角、低分辨率模板匹配中的应用前景分析本文研究了一种基于多视角变换空间优化搜索的模板匹配方法,解决了航空图像拍摄视角多变、分辨率差异大等情况下模板目标检测的问题。实验证明,所提方法对图像模糊、高斯噪声和有损压缩等图像退化具有较好的适应能力,在大差异视角和低分辨率模板匹配中具有更好的稳定性,并且具有单模板多目标检测的能力,无需大量目标图像训练学习。由于所提方法对模板与实际图像的姿态差异适应性强