一种平移旋转图像的角点匹配方法

王小鹏，房超，雷涛

兰州交通大学电子与信息工程学院，兰州 730070

一种平移旋转图像的角点匹配方法

王小鹏，房超，雷涛

兰州交通大学电子与信息工程学院，兰州 730070

在图像角点匹配过程中，目标图像往往存在平移旋转现象，直接影响匹配效果，为此提出了一种平移旋转图像的角点匹配方法。该方法首先利用角点检测生成自相关矩阵的梯度信息与仿射变换相结合，构造确定性退火算法中的自由能函数，然后对该自由能函数进行优化，获取待匹配角点间的仿射变换参数，最后利用该变换参数实现角点匹配。实验结果表明，该方法能够在目标图像发生平移旋转的情况下，有效实现角点匹配。

角点匹配；平移旋转；确定性退火；仿射变换

1 引言

角点匹配指利用同一场景中采集到的两幅图像角点信息，确定待匹配角点间相对位置关系的过程，在数字图像处理、计算机视觉以及和模式识别等领域有重要应用价值。目前已提出了许多角点匹配算法，其中基于图像点特征及灰度信息的角点匹配算法[1]，利用局部灰度相关实现角点匹配；基于位置相似性特征的角点匹配算法[2]，利用局部范围内对应点的相对位置不变作为约束条件实现角点匹配；基于Hausdorff距离的角点匹配[3]，利用待匹配角点间的Hausdorff距离实现角点匹配；基于图像亮度相关的角点匹配[4]，利用光流法与一阶差分技术实现角点匹配；基于确定性退火技术鲁棒性点匹配算法[5]，利用匹配矩阵估计方法构造自由能函数，最终实现角点匹配。

在图像采集过程中，由于拍摄角度不同会导致图像在空间上存在平移、旋转等差异，这些差异会影响角点匹配的精度。由于仿射变换[6]能够有效获取图像间的平移和旋转参数，从而可以消除平移旋转等对角点匹配的影响。通过仿射变换的同素性与平行性可将角点匹配过程转化为求解角点间仿射变换参数的过程。为此本文将角点检测与确定性退火技术[7]相结合，利用角点检测时生成自相关矩阵梯度信息构造退火过程的自由能函数，并运用确定性退火技术自由能函数收敛到全局最优解的性质，对角点匹配自由能函数进行优化处理，获取两匹配图像角点间的仿射变换参数，最后通过该参数实现角点匹配。

2 角点匹配流程

提出的角点匹配流程如图1所示。首先利用Harris算子[8]对目标和模板图像分别进行角点检测，然后将确定性退火技术应用于角点匹配过程中，通过构造自由能函数与优化自由能函数获取待匹配角点间的仿射变换参数，最后利用该参数实现角点匹配。

图1 角点匹配流程图

3 Harris角点检测

Harris角点检测[9]是基于图像灰度的检测，通过计算像素点所在位置的梯度变化来检测角点，若像素点所在位置x方向梯度与y方向梯度的绝对值均较大，则将该像素点判定为角点。

其中detM=λ1×λ2，trM是矩阵M的迹，且trM=λ1+λ2，k为大于零的参数。通常，detM在边缘处较小而在角点处较大，而trM在边缘和角点处则保持一致。因此，当像素点(x，y)的Rh值为局部最大时，即为角点。

4 仿射变换参数确定

当获取目标和模板图像的角点信息后，如何对角点进行匹配直接关系到匹配精度。由于目标图像可能存在平移旋转，因此如何获取最优的仿射变换参数是实现匹配结果的关键，求得的仿射变换参数一方面应能消除平移旋转的影响，另一方面应能保证更多的匹配点数。为此，本文运用确定性退火过程来获取最优仿射变换参数。

确定性退火技术是依据自然法则提出的一种求解全局最优解的拟自然方法，将求解一系列随温度变化的物理系统自由能函数极小值思想引入到求解优化问题，它能使算法直接得到全局极小值，无需考虑局部极小值对优化问题的影响。

退火过程利用自由能减少定律描述系统在每一温度下达到平衡态的过程。由自由能减少定律可得：

其中E(x)是指某一物理系统的能量，当系统达到平衡状态时自由能函数达到极小值。确定性退火技术要求构造物理系统式（2）对应的自由能函数F(x，T)。此函数F(x，T)应满足：

（1）当T=∞时，F(x，T)的全局极小值易求出。

（2）当T=0时，F(x，T)=E(x)。确定性退火技术就是将系统在T=T+ΔT时的自由能函数的极小值xmin(T+ΔT)作为初始值，通过求解m inF(x，T)的极小值来模拟系统达到平衡状态的过程。确定性退火的求解过程如下：

步骤1确定系统自由能函数F(x，T)，使F(x，T)满足上述两个条件。

步骤2初始化T=T0，记xmin(Tk)为m inF(x，Tk)的最优解。

步骤3Tk+1=αTk(0＜α＜1)，以xmin(T0)为初始值求解m inF(x，Tk+1)，记相应最优解为xmin(Tk+1)，其中α为退火速率。

步骤4判断Tk是否收敛，若满足则停止，则xmin(Tk+1)为最优解，否则执行下一步。

步骤5k=k+1，执行步骤3。

4.1 自由能函数构造

能否构造出合适的自由能函数是角点匹配的关键，构造出的自由能函数应包含待匹配角点间的仿射变换参数。为了求取最优仿射变换参数，将仿射变换与角点检测中自相关矩阵梯度[10]信息结合构造自由能函数。

仿射变换的一般表达式为：

其中PA={(xa1,ya1),(xa2,ya2),(xa3,ya3),…,(xam,yam)}和PB= {(xb1，yb1)，(xb2，yb2)，(xb3，yb3)，…，(xbn，ybn)}，分别表示目标图像与模板图像中待匹配的角点坐标，A是旋转矩阵，T为平移矩阵。旋转和平移参数矩阵决定了待匹配角点间的坐标变换关系。设V为仿射变换算子，则二维空间的仿射变换可表示为：

其中θ为旋转角度，tx，ty为平移量。

由角点检测自相关矩阵M可知，XY梯度算子包含了水平与垂直方向的梯度信息。因此利用X和Y的乘积重新描述每一个角点。假设GXY为某一角点在水平与垂直方向的梯度值之积，则可将通过仿射变换后的目标图像与模板图像角点的GXY绝对值差之和GXY作为角点是否匹配的依据，即：

其中P与Q是两个ω×ω大小的窗口，其中心位于待匹配角点，ε为给定阈值，a和b分别是P与Q中的角点。当GXY值最小时，则可以判定两个角点匹配。

E(θ，tx，ty)值表征在仿射变换V的作用下，两个角点集PA与PB的匹配点数。物理退火过程的自由能函数采用Boltzman概率分布，其分布表示为：

其中，EN为新能量值，E为原始能量，T为温度值，ΔE=EN-E。

根据能量函数可以构造出如下函数：

由于F(θ，tx，ty，T)具有上述两个性质，因此可以将其作为角点匹配时的自由能函数。

4.2 自由能函数优化

自由能函数优化的目的是为了求取最优的仿射变换参数，利用该参数对待匹配点集进行匹配，获得角点集之间的对应关系实现角点匹配。

自由能函数优化处理步骤如下：

步骤1退火系统初始化：T=T0，θ=θ0，tx=tx0，ty=ty0，系统最小温度Tmin，系统退火速率α。

步骤2自由能函数的优化：当系统温度T≥Tmin时，利用共轭梯度算法对自由能函数进行处理，求得一组平移与旋转参数，然后将系统温度T乘以退火速率α作为新的系统温度T，与系统最小温度Tmin进行比较，若T≥Tmin，则继续上述处理；否则停止运算，并输出自由能函数最小值：m inF(θ，tx，ty，T)=V(θ，tx，ty)，此时获取的(θ，tx，ty)为最优仿射变换参数。

步骤3利用最优仿射变换参数对PB中的点进行坐标变换得到PB'，将PA与PB'中的点进行匹配，其中PB'=V(θ，tx，ty)PB。

5 角点匹配

角点匹配的目的是确定待匹配角点间的对应关系，利用Harris角点检测算法分别获取待匹配图像的角点后，运用自由能函数优化求取的最优仿射变换参数对角点进行匹配。具体步骤如下：

步骤1利用自由能函数最小化求取最优仿射变换参数V(θ，tx，ty)，对PB进行仿射变换得到PB'。

步骤2利用式（5）将待匹配角点进行比较，当GXY的值达到最小时，则判定两个角点匹配。

步骤3所有待匹配角点依次执行步骤2，完成角点匹配。

6 实验结果

为了验证方法的有效性，在MATLAB平台上进行了仿真。模板图像和目标图像均为420×255像素大小，图2（a）和（b）分别为模板和目标图像，图2（b）相对于图2（a）存在平移和旋转现象。首先利用Harris算法对两幅图像进行角点检测，结果如图2（白色十字为检测出的角点）所示。

图2 Harris算法角点检测结果

利用本文方法对检测到的角点进行匹配，其中阈值ε=1，初始值T0=100，θ=0°，tx=0，ty=0，Tmin=0.1，退火速率α=0.8，匹配所选用窗口大小为5×5（通常取奇数对），通过自由能函数优化后得到的仿射变换参数为：θ=13°，tx=46 pix，ty=9 pix。角点匹配结果如图3所示，其中白色十字为匹配角点。

图3 本文角点匹配方法

为了验证该方法性能，在图2角点检测的基础上，分别采用基于Hausdorff距离[11]的角点匹配和基于归一化互相关（NCC）[12]的角点匹配方法进行了角点匹配，匹配结果分别如图4和图5所示。可以看出，本文方法的匹配点数（具体如表1）明显多于其他两种方法。这表明在利用仿射变换参数实现角点匹配时，本文方法充分利用了图像的特征信息，获取了最优的仿射变换参数。

图4 基于Hausdorff距离的角点匹配

图5 基于归一化互相关的角点匹配

从表1也可以看出，本文方法的运算复杂度低于Hausdorff距离的角点匹配，但高于NCC角点匹配方法，但匹配效果明显优于其他两种方法。

表1 不同匹配方法的匹配点数及运算时间对比

7 结论

对于图像角点匹配过程中由于目标图像存在平移旋转对匹配造成的影响。将角点检测时生成的自相关矩阵梯度信息与仿射变换结合，通过确定性退火过程中的自由能函数构造以及优化获取最优的仿射变换参数，并以此实现角点匹配。通过自相关矩阵的梯度信息构造自由能函数，充分利用了图像中的特征信息，在一定程度上降低了构造自由能函数的复杂度。由于获取了最优的仿射变换参数，因而匹配效果较好。

[1]曹晓光，徐琳，郁文霞.基于角点检测的高精度点匹配算法[J].仪器仪表学报，2006，27（6）：1269-1271.

[2]潘俊君，张艳宁.相关视觉中基于位置相似性特征的点匹配问题研究[J].中国图象图形学报，2005，10（1）：80-86.

[3]Huttenlocher D P，K landerman G A，Rucklidge W J.Comparing image using the Hausdorff distance[J].IEEE Trans PAM I，1993，15（9）：850-863.

[4]Georgescu B，Meer P.Point matching under large image deformations and illum ination changes[J].IEEE Transactions on Pattern Analysis and Machine Intelligence，2004，26（6）：647-688.

[5]孙东梅，裘正定.基于确定性退火技术的鲁棒性点匹配算法[J].计算机学报，2002，25（6）：606-611.

[6]Aw rangjeb M，Lu Guojun.An improved curvature scale-space corner detector and a robust corner matching approach[J]. IEEE Transactions on Image Processing，2008，17（12）：2425-2441.

[7]杨广文，李晓明.确定性退火技术[J].计算机学报，1998，21（8）：765-768.

[8]Harris C，Stephens M.A combined corner and edge detector[C]// Proceedings of the 4th A lvey Vision Conference，Manchester，1988：147-151.

[9]赵万金，龚声蓉.一种自适应的Harris角点检测算法[J].计算机工程，2008，34（10）：212-214.

[10]Alkaabi S，Deravi F.Iterative corner extraction and matching for mosaic construction[C]//Proceeding of 2nd Computer and Robot Vision，British Columbia，Canada，2005：468-475.

[11]孙瑾，顾宏武.一种鲁棒性Hausdorff距离图像匹配方法[J].中国图像图形学报，2008，13（4）：761-767.

[12]郭伟，赵亦工.一种改进的红外图像归一化互相关匹配算法[J].光子学报，2009，38（1）：189-193.

WANG Xiaopeng,FANG Chao,LEI Tao

School of Electronic&Information Engineering,Lanzhou Jiaotong University,Lanzhou 730070,China

During the course of image corner matching,the translation and rotation of object image often affect the matching results.A corner matching method is proposed based on deterministic annealing.Harris corner detection is used to extract the corner points respectively from object and matching image,and the gradient information of the corner points from the autocorrelation matrix are also calculated.The free energy function of deterministic annealing is constructed by combining the gradient information and the affine transform.The optimization affine transform parameters are obtained by optimizing the free energy function.Corner matching between object and matching image are complemented through the affine transform.Simulations show that this method can effectively achieve the corner matching when the object image occurring translation and rotation.

corner matching;translation and rotation;deterministic annealing;affine transform

A

TP391.4

10.3778/j.issn.1002-8331.1209-0290

WANG Xiaopeng,FANG Chao,LEI Tao.Corner matching for translation and rotation image.Computer Engineering and Applications,2014,50（16）：173-176.

国家自然科学基金（No.61261029，No.61202314）；甘肃省高等学校硕士生导师科研项目（No.1104-4）。

王小鹏（1969—），博士，教授，研究方向：图像分析与识别；房超（1987—），硕士研究生，研究方向：图像处理；雷涛（1981—），博士，副教授，主要研究方向：数字图像分析。E-mail：wangxp1969@sina.com

2012-09-25

2012-11-08

1002-8331（2014）16-0173-04

CNKI网络优先出版：2012-12-18,http://www.cnki.net/kcms/detail/11.2127.TP.20121218.1528.023.htm l