第22卷第4期2010年4月
计算机辅助设计与图形学学报
Journal of Computer 2Aided Design &Computer Graphics
Vol.22No.4Apr.2010
收稿日期:2009-04-16;修回日期:2009-10-20.基金项目:国家自然科学基金(50875130);高等学校博士点专项科研基金(200802870016);
江苏省科技支撑计划(BE2008136).韦 虎(1974—),男,博士研究生,主要研究方向为非接触三维几何测量、逆向工程、CAD ;张丽艳(1967—),女,博士,教授,博士生导师,主要研究方向为非接触三维几何测量、机器视觉检测、逆向工程;刘胜兰(1972—),女,博士,副教授,主要研究方向为逆向工程、CAD ΠCAM ;石春琴(1983—),女,博士研究生,主要研究方向为逆向工程、非接触三维几何测量.
基于SIFT 图像特征匹配的多视角深度图配准算法
韦 虎,张丽艳,刘胜兰,石春琴
(南京航空航天大学机电学院 南京 210016)(weihu2005@https://www.doczj.com/doc/e914812552.html, )
摘要:为有效地解决多视角深度图配准问题,提出一种新的配准算法.首先给出一种深度图数据图像化方法,根据
深度图包含的像素信息和网格顶点处的曲率值创建特征图像;然后通过对特征图像进行SIF T 特征检测与匹配来获得特征点与匹配关系,从而得到原始深度图上的特征点与匹配关系;最后采用投票和预配准方法去除误匹配,实现递增式多视角深度图配准.模拟噪声实验和多个实际测量深度图的配准实验结果验证了该算法的鲁棒性和有效性.关键词:双目立体测量;多视角深度图;配准;SIF T 算法;特征匹配中图法分类号:TP391
An Algorithm on R egistration of Multi 2vie w R ange Images B ased on SIFT Feature Matching
Wei Hu ,Zhang Liyan ,Liu Shenglan ,and Shi Chunqin
(College of Mechanical and Elect ronic Engineering ,N anj i ng Uni versit y of A eronautics and A st ronautics ,N anj ing 210016)
Abstract :A novel algorit hm on regist ration of multi 2view range images is proposed.Firstly ,a met hod for t ransferring a range image to a feat ure image is performed ,where t he pixel information and t he curvat ure information on t he range image is used.Secondly ,t he keypoint s and t heir matching relationship s o n t he feat ure images are constructed by using t he SIF T algorit hm.The matching relationship s among t he original range images are obtained https://www.doczj.com/doc/e914812552.html,stly ,false matches are deleted by a voting and pre 2registering scheme ,and t hen multi 2view range images are registered incrementally into a common f rame according to t he correct matches.Experimental result s o n bot h synt hetic and real models demo nstrate t hat t he algorit hm is robust and effective.
K ey w ords :binocular stereo vision ;multi 2view range images ;regist ration ;SIF T algorit hm ;feat ure matching
双目立体测量在零件的尺寸检测[122]、模型的三维外形测量[324]等领域有着广泛的应用.在三维外形测量中,要想获取物体的完整表面三维数据,必须将多次测量得到的深度图数据(多视图)配准到同一坐标系中.深度图配准技术主要分为2类:1)通过辅助硬件设备完成.例如利用旋转台来获取物体与测量设备之间的相对位置变换[5],或者在物体表面粘贴
易识别的标记点、通过多视图之间相同标记点的匹配来建立多视图间的坐标变换矩阵[6].这类技术适用范围比较广,但是增加了测量系统的复杂性或者破坏了被测物体表面纹理.2)通过多视图内在的特征点进行配准[7].配准过程主要包括特征点的检测和匹配,这一类技术问题也广泛地存在于图像领域[8].为检测图像上内在特征点,一种有效方法是在
二维图像的基础上引入第三维———尺度,建立图像的尺度空间.Lindeberg [9]提出二维尺度空间理论和同时在多个尺度下进行的图像特征检测算法;Lowe [10]在
此基础上提出一种尺度不变特征变换(SIF T )的特征检测与匹配算法,SIF T 特征点定位准确,具有尺度、旋转、视角和亮度不变性,而且对仿射变换具有一定的鲁棒性.实验表明,SIF T 算子优于其他局部特征提取算子[11].
借鉴尺度空间在图像特征点检测与匹配方面的成功运用,有学者将尺度空间的方法推广到三维网格的特征检测上,并取得一定的效果.Lee 等[12]采用不同尺度的高斯核函数对平均曲率进行加权平均,并对相邻尺度间的高斯加权平均曲率求差分,通过非线性组合算子对所求差分进行求和得到网格顶点的特征值,并将特征值中的局部极值点定义为网格特征点.Schlatt mann [13]受基于尺度空间的图像角点检测算法启发,利用保持体积的平均曲率流算法建立三维网格上的尺度空间,提取各个尺度下的特征值,并以局部极值点作为网格特征点.Novatnack 等[14]将三维网格转化为二维图像来检测网格上的特征,先通过法矢映射将三维网格映射为二维图像;然后在图像上检测特征,并通过映射关系得到网格上对应特征,该方法可以同时检测出网格上的特征点与特征线.但是,文献[12214]对提取得到的特征点建立相应匹配算法比较困难.
本文针对双目立体测量系统[324]中的多视图配准,利用该系统测量得到的深度图数据包含像素信息的特点,建立了深度图网格顶点到二维像素点之间的映射关系;再根据深度图网格顶点处局部微分性质确定对应像素点处的灰度值,从而可以将尺度空间的思想通过图像转化应用到深度图网格上.本文算法的主要思路是,采用深度图网格顶点的曲率值,并计算其刚性变换不变性度量作为二维图像上的灰度值,创建二维灰度特征图像;利用SIF T 算法对灰度图像进行特征点检测与匹配,通过映射关系建立多视图上的特征点及其匹配关系,再根据多视图匹配特征点之间的欧氏距离不变性剔除误匹配;最后根据正确的匹配特征点计算变换矩阵,以实现多视图配准.
1 SIFT 特征检测与匹配
SIF T 算法是Lowe [10]在总结了现有基于不变
量技术的特征检测方法基础上,提出的一种基于尺度空间的图像局部特征描述算法,该算法已经在图像匹配、全景拼接和视觉导航等领域得到成功应用.SIF T 算法主要分为检测尺度空间特征点,定义特征点主方向,生成特征向量描述子和特征向量描述子匹配4步.
1.1 检测尺度空间特征点
文献[9]证明了高斯卷积核是实现尺度变换的唯一变换核,而且是唯一的线性核.利用高斯卷积核可以计算得到二维图像I (x ,y )的高斯2拉普拉斯(Laplacian
of G aussian ,Lo G )尺度空间L (x ,y ,σ
)=G (x ,y ,σ)3I (x ,y ),其中(x ,y )是像素坐标,σ是尺度坐标.尺度
可变高斯函数为G (x ,y ,σ
)=1
2
πσ2
e -
(x 2+y 2)Π2
σ2.
为了有效地在尺度空间检测到稳定的特征点,
Lowe 提出了高斯差分(difference of Gaussian ,Do G )尺度空间.Do G 算子计算简单,是尺度归一化的Lo G 算子的近似,它由Lo G 尺度空间中相邻尺度2幅图像相减得到.Do G 尺度空间可以表示为
D (x ,y ,σ
)=L (x ,y ,k σ)-L (x ,y ,σ),其中k 为常数因子.通过计算采样点在每一尺度下Do G 算子的值,可以得到特征尺度轨迹曲线,曲线的局部极值点即为该采样点尺度.为了寻找尺度空间的极值点,每个采样点需要和与它同尺度的8个相邻点,以及上下相邻尺度对应的9×2个点共26个点相比较,如果该取样点的Do G 算子值在这26个邻域中为极值,则将该点定义为特征点.对所有的特征点,再通过拟合三维二次函数以精确确定特征点所在Lo G 尺度空间的像素位置和尺度坐标,同时去除低对比度的特征点和不稳定的边缘响应点,以增强匹配稳定性、提高抗噪声能力.1.2 定义特征点主方向
利用特征点邻域内像素的梯度方向分布特性为每个特征点定义主方向,使特征点的描述子具备旋转不变性.在Lo G 尺度空间中,每个像素的梯度模和方向分别为
m (x ,y )=
(L (x +1,y )-L (x -1,y )2+(L (x ,y +1)-L (x ,y -1))2,
θ(x ,y )=arctan ((L (x ,y +1)-L (x ,y -1))Π((L (x +1,y )-L (x -1,y )));
并利用Lo G 尺度空间中的特征点邻域内像素点
创建梯度方向直方图.直方图以每10°作为一个柱,
5
56第4期韦 虎,等:基于SIFT 图像特征匹配的多视角深度图配准算法
共36个柱,然后将邻域内的每个像素点按梯度方向θ归入适当的柱,以梯度模m 作为贡献的权重;最后选择直方图的主峰值作为该特征点的主方向.为增强匹配的鲁棒性,选取量值达到主峰值80%以上的局部峰值作为辅助方向.1.3 生成特征向量描述子
首先将坐标轴旋转为特征点的主方向,以确保
旋转不变性;然后以特征点为中心取8×8的窗口.如图1[10]所示,图1a 中每个小格代表特征点所在尺度空间中其邻域内的一个像素,箭头方向代表该像素的梯度方向,箭头长度代表梯度模值,圆圈代表高斯加权的范围(越靠近特征点的像素梯度方向信息贡献越大).然后在每4×4的小块上计算8个梯度方向的累加值,绘制每个方向的直方图,即可形成一个种子点,如图1b 所示,其中一个特征点由2×2共4个种子点组成,每个种子点为一组8维向量(8个方向信息).这种邻域方向信息联合的思想增强了算法抗噪声的能力,同时对于含有定位误差的特征匹配也提供了较好的容错性
.
图1 生成SIFT 特征点描述子
实际计算过程中,为了增强匹配的稳健性,
Lowe 建议对每个特征点使用4×4共16个种子点来描述,因此对于每一个特征点可以生成一组128维的特征向量描述子.此时描述子已经去除了尺度变化、旋转等几何变形因素的影响,再将描述子归一化,则可以进一步去除光照变化的影响.1.4 特征向量描述子匹配
对2幅待匹配的图像,计算第一幅图像中每个特征点与第二幅图像中每个特征点的对应描述子向量之间的欧氏距离,将第二幅图像中距离值最小的特征点作为第一幅图像特征点的匹配点.为了减少误匹配率,Lowe 计算最近距离与次近距离的比值ratio,只有当ratio 小于给定阈值r _t h 时,才认为该匹配是正确匹配.
2 深度图配准
在双目立体测量过程中,摄像机需从不同的景
深和角度位置对被测物体进行拍摄,因此测量得到
的多视图之间会产生一定的尺度变化和旋转变化.为有效地实现深度图的自动配准,本文将深度图数据图像化,从图像的角度利用SIF T 算法进行特征点检测与匹配,最终实现多视图的配准.2.1 深度图数据图像化
用R (V ,Q )表示一幅深度图,V ={v i },v i ∈3表示深度图中空间点坐标,Q ={q i },q i ∈2表示v i 点在左相机成像平面上的像素坐标.对深度图R 上的所有空间点集V ,计算其对应像素的包围盒B ox
(q min ,q max ),其中q min ,q max 分别是包围盒的2个对角
点像素坐标,创建与B ox 同样大小的深度图特征图像I R ,记p i =q i -q min ,P ={p i },则深度图R 上任意一空间点v i 可以与特征图像I R 上像素点p i 相对应.为简便起见,记这种对应关系为映射
f :V →P ,
v i |→f (v i )=p i =q i -q min .
显然f 为一一映射,仅当p ∈P 时,p 点在V 中有原象v =f -1(p ),而对特征图像I R 上其他像素点,则不存在深度图上空间点与之对应,如图2所示
.
图2 深度图转化为特征图像
为使得特征图像能反映深度图的特征,要求特征图像上的灰度值(如图2b 所示)必须为深度图自
身内在的特征度量,这种度量应该具有刚性变换不变性和对噪声的鲁棒性.本文采用深度图空间点处的曲率作为特征度量,将其转化为对应像素点处的灰度值.
首先根据深度图R (V ,Q )包含的像素信息对深度图进行三角化,并估计每个网格顶点处法矢[4].为增加曲率估计对噪声的鲁棒性,本文以网格顶点的22邻域为支撑区域计算平均曲率和高斯曲率[15].对于网格上的每个顶点v ,通过上述方法估计其高斯曲率K G (v )和平均曲率K H (v ),记
F (v )=
K 2
H (v )-λ?K G (v )Π2;
其中λ为特征参数.本文定义F (v )为深度图空间点
的特征度量,将F (v )的值转化为特征图像I R 上对
6
56计算机辅助设计与图形学学报 第22卷
应像素点f (v )处的灰度值,而图像上其他像素点处
的灰度值赋值为255.计算特征图像I R 上每一像素点的灰度值
I R (p )
=
255[1-(F (f
-1
(p ))-F min )Π
(F max -F min )],p ∈P
255,p
P
(1)
其中F max 和F min 分别为V 中所有空间点的特征度量F (v )的最大值和最小值.特征参数λ为经验常数,选取不同λ值,深度图转化为特征图像的结果将有所区别.对多个实际测量模型进行不同λ值的配准实验表明,λ值在区间[0.3,0.7]内时,正确匹配特征点对数以及与全部可能匹配特征点对数的比值较高,配准过程稳定可靠,本文在实验中均取λ=0.45.将图2a 所示深度图进行图像化后的特征图像如图2b 所示.
对2幅有部分重叠的深度图分别进行图像化处理后,对应的特征图像上会有部分重叠的区域,由于视角以及景深的不同,会使2幅图像之间的重叠区域部分产生一定的旋转、尺度变化以及仿射变换.式(1)实际上是将特征值线性变换到灰度值区间[0,255]上,F min 对应灰度值为255,F max 对应灰度值为
0,中间值线性变换成相应的灰度值.对于2幅有重
叠的深度图来说,理论上重叠部分的特征值是相同的,而非重叠部分可能会导致2幅深度图的F min 和F max 有所不同.因此,利用式(1)可能使得相同特征值转化成为不同的灰度值,从而引起图像上重叠部分的亮度差异.由于SIF T 算法在处理这些变化和差异时具有较强的鲁棒性,本文采用SIF T 算法对特征图像进行特征检测与匹配.2.2 特征点检测
以图2所测量的模型为例,利用双目立体测量系统从不同角度测量得到2幅深度图,记为R 1和R 2.根据第2.1节方法,建立相应的映射f 1和f 2以及特征图像I R 1和I R 2,对特征图像I R 1和I R 2利用SIF T 算法检测得到特征图像上特征点.本文的SIF T 算法相关代码主要参照了Rob Hess (http :ΠΠhttps://www.doczj.com/doc/e914812552.html, Π～hess Π
)提供的代码.如图3a 所示,图中“+”位置表示特征点的像素位置,显然部分特征点并不在深度图空间点所对应的
象中.因此,由SIF T 检测出的特征点像素坐标p ,根据相应的映射f ,仅当p ∈f (V )时,定义v =f -1(p )为深度图上的特征点,如图3b 中的圆点所示.
图3 两视图特征检测与匹配
2.3 特征点匹配与优化
按第1.4节的方法首先对图像上的特征点进行
匹配,在匹配关系查找方面,文献[16]提出一种双向匹配算法,该算法分别从2幅图像出发,到另一匹配图像上查找匹配特征点,再对2组匹配关系求交,减少了误匹配的数量.本文同样采用双向匹配算法查找匹配特征点,与文献[16]不同的是,本文采用对2组匹配关系求并的方法得到最终的匹配特征点,显然本文算法在增加正确匹配个数的同时也增加了
误匹配的数量.选择这种方法是由于图像与深度图之间的映射关系,使得误匹配特征点在本文算法中可以比较容易被去除,而保留下更多的正确匹配关系,以增强多视图配准的稳健性.
将双向匹配得到的匹配关系(如图3c 中对应图像特征点之间的连线所示)根据图像与深度图之间的映射,转化成深度图特征点之间的匹配关系(如图3d 所示).对于2幅深度图中正确匹配的特征点集,属于同一深度图的特征点之间的欧氏距离与
7
56第4期韦 虎,等:基于SIFT 图像特征匹配的多视角深度图配准算法
另一深度图上相匹配特征点之间的欧氏距离应该是相等的.基于这个原则,在全部的匹配点集中根据特征点之间欧氏距离是否相等进行投票,保留投票得数超过一定数量的匹配关系,去除票数较低的匹配
关系.设{v 1k },{v 2
k }分别表示深度图R 1和R 2上相匹配的对应特征点,k =1,2,…,N ,N 为匹配个数,为
每对点(v 1k ,v 2
k )之间的匹配关系建立累加器V O T k 对投票结果进行统计,用‖v 1k v 2
k ‖表示两点之间的欧氏距离,投票算法伪代码如下:
input {v 1k },{v 2
k },k =1,2,…,N
output {V O T k }
for i =1,2,…,N for j =1,2,…,N
if ‖v 1i v 1j ‖==‖v 2i v 2j ‖
then V O T i add 1;
在投票算法中,当且仅当‖v 1i v 1j ‖与‖v 2i v 2j ‖差的绝对值小于d 1时,认为‖v 1i v 1
j ‖
等于‖v 2i v 2j ‖,本文中取d 1为深度图网格边长的平均值.当累加器的
数量小于给定的阈值时,则认为相应的匹配关系为误匹配,而保留其他的匹配特征点.理论上,至少有3对以上的正确匹配特征点对就可以实现两视图的配准.为增加配准算法的稳定性,在本文配准过程中要求至少有5对以上的正确匹配特征点参与配准.
假设(v 1k ,v 2
k ),k =1,2,…,N 中至少含有5对以上正确匹配特征点,根据投票算法,则每对正确匹配特征点至少可以得到4票,因此取累加器阈值为4可以确保不会误删除正确的匹配特征点.
单纯依靠累加器阈值并不能完全去除误匹配,
本文采用预配准的方法对保留的匹配特征点进一步
进行优化.首先将保留的匹配特征点利用SVD 方法求解变换矩阵[6],计算配准后特征点之间的平均误差为d 2,并记d =max (d 1,d 2);再将原始的{v 1k },
{v 2
k },k =1,2,…,N 用求得的矩阵作相应的坐标
变换,重新计算变换后的所有匹配特征点之间距离,去除距离大于d 的特征点所对应的匹配关系,剩下的匹配关系则认为是正确的.对图3d 中全部匹配特征点运用本节算法得到正确匹配结果,如图3e 所示.
2.4 多视图配准
根据得到的正确匹配特征点,由SVD 方法计算
相应变换矩阵,即可实现两视图的配准.为实现递增式多视图的配准,对已配准的深度图,首先合并各个深度图上特征点及其特征图像上的图像特征点;然后对新增加的深度图数据进行图像化、SIF T 特征检测,将得到的图像特征点集与先前合并图像特征点集进行双向匹配,并根据深度图与特征图像之间的映射关系,建立新深度图上特征点与先前合并深度图上特征点之间的匹配关系;最后根据第2.3节的方法对匹配关系进行投票和预配准优化以去除误匹配,利用SVD 方法计算新深度图所对应的变换矩阵,将其配准到已配准的深度图坐标系中.重复上述过程即可实现递增式多视图的配准.
对图3测量的实物进行不同角度的测量,得到5幅深度图.如图4a 所示,利用本文算法实现递增
式多视图配准,最终配准结果如图4b 所示,图4c 所示为经过多视图全局配准优化[6]与多视图同时融合[4]后的结果
.
图4 多视图配准
3 实验结果及分析
在对深度图数据图像化的过程中,当2幅深度
图的F max 或F min 不相同时,会引起特征图像重叠部分的亮度差异.由于F min 通常比较小(接近于0),因此本文设计模拟噪声实验仅对F max 施加一定的扰
动,以验证配准算法对不同F max 的鲁棒性.将式(1)
改为
I R (p )=
255[1-(F (f
-1
(p ))-F min )Π
(F max ?
ε-F min )],p ∈P 255,p
P
(2)
其中ε为扰动因子.以图3b 中2幅深度图为例,对第一幅深度图按式(1)进行灰度转化;对第二幅
8
56计算机辅助设计与图形学学报 第22卷
深度图的F max 分别施加±50%的干扰,即以式(2)进
行灰度转化,并分别取ε=1.5和ε=0.5,特征图像如图5所示.从图5a ,5b 的左边特征图像中可以看出,重叠区域存在明显的亮度差异,中间和右边图分别是对应深度图特征匹配和去除误匹配后的结果,它们与图3中的实验结果相比,正确匹配特征点对数虽然有所减少,但是仍然可以提取较多的正确匹配特征点,说明了本文算法对F max 的扰动具有较强的鲁棒性
.
图7
不同景深和视角下的深度图配准实验
图5 对F max 施加扰动的深度图配准实验
本文利用深度图空间点的曲率作为灰度值的转化依据,由于网格的离散曲率值估计对噪声比较敏
感,因此本文采用鲁棒性较强的算法计算法矢和曲率;同时结合SIF T 算法,有效地克服了一定范围内的噪声影响.对图3中的2幅深度图分别添加均值为0、标准差为σ的随机噪声,取σ=0.1%L ,L 表示深度图的空间包围盒的对角线长度.对添加噪声后的深度图运用本文算法进行如图6所示实验,结果表明该算法对噪声具有一定的鲁棒性
.
图6 随机噪声下的深度图配准实验
在测量过程中,被测物体与相机之间的位置经常需要调整,会造成测量景深与拍摄视角的变化,进而会引起2幅特征图像重叠区域的旋转、尺度变化和仿射变换.图7所示为对同一模型在不同景深和不同视角下测量得到的2幅深度图进行的配准实验,图中2幅深度图的景深分别约为90cm 和70cm ,相对旋转角度约为180°.实验结果表明,本文算法适用于不同景深和视角下的深度图.
图8～10所示分别为本文算法应用于3种不同模型的配准实验,实验结果说明该算法具有较为广泛的适用范围.
在图3和图5～10配准实验中,深度图与特征图像的特征点及匹配数据如表1所示.表1中,N IF 和N RF 分别表示在特征图像与深度图上检测得到的
9
56第4期韦 虎,等:基于SIFT 图像特征匹配的多视角深度图配准算法
图8
钣金深度图配准实验
图9
佛像深度图配准实验
图10 花瓶深度图配准实验
特征点个数(“Π”两边分别表示相应的两组特征点的
个数),N IMF 和N RMF 分别表示在特征图像与深度图上特征点的匹配对数,N RCMF 表示深度图上最终正确的匹配特征点对数.从以上的实验和表1中可以看
出,当深度图上细节比较丰富时(如图9,10所示),
N IF 和N RF 较多,相应的N RMF 和N RCMF 也较多;反之,
当深度图细节较少(如图8所示)或者含有较大的噪声(如图6所示)时,所得到的N IF 和N RF 较少,相应的N RMF 和N RCMF 也较少.另外,N RCMF 的值还取决于2幅深度图重叠区域的大小和形状,当N RCMF 的值大
于5时(见第2.3节中投票算法),本文算法是稳定
有效的.
表1 深度图配准实验的相关数据
模型N IF
N RF
N I MF
N RMF
N RCMF
图3259Π349169Π216595427图5a 259Π469169Π311605324图5b 259Π284169Π284514822图6444Π311304Π205484213图7128Π13098Π100514838图8213Π201154Π146736941图9748Π703497Π425988444图10
303Π337
225Π265
90
84
79
66计算机辅助设计与图形学学报 第22卷
4 总 结
针对在双目立体测量系统测量得到的深度图具有像素信息这一条件,本文提出了一种多视图配准算法,将深度图的配准问题转化为特征图像上的特征检测与匹配问题,有效地解决了多视图的配准.实验结果表明,该算法具有较强的鲁棒性,适用范围较广.本文算法虽然针对包含像素信息的深度图,但是这个限制不是必须的,可以考虑将深度图通过其他途径实现其图像化.今后我们将在不考虑深度图像素信息的前提下推广本文算法,使其具有更广泛的应用领域.
致谢 本文共享了Rob Hess的SIFT算法相关C语言代码,在此表示感谢!
参考文献(R eferences):
[1]Guo Jin,Liu Xianyong,Chen Xiaoning.Automatic
measurement of t he mechanical part based on binocular stereo vision[C]ΠΠProceedings of t he7t h World Congress on Intelligent Control and Automation,Chongqing,2008:84872 8491(in Chinese)
(郭 进,刘先勇,陈小宁.基于双目视觉的机械零件自动检测研究[C]ΠΠ第七届全球智能控制与自动化大会论文集,重庆,2008:848728491)
[2]Zheng Y,Liu Y.Closed2form solution for circle pose
estimation using binocular stereo vision[J].Electronics Letters,2008,44(21):124621247
[3]Zhang Hui,Zhang Liyan,Chen Jiang,et al.Field calibration
of binocular stereo system based on planar template and free snapping[J].Acta Aeronauticaet Astronautica Sinica,2007, 28(3):6952701(in Chinese)
(张 辉,张丽艳,陈 江,等.基于平面模板自由拍摄的双目立体测量系统的现场标定[J].航空学报,2007,28(3): 6952701)
[4]Wei Hu,Zhang Liyan,Zhang Hui.An approach for
simultaneous integration of range images in binocular stereo vision[J].Journal of Computer2Aided Design&Computer
Graphics,2008,20(11):144621451(in Chinese)
(韦 虎,张丽艳,张 辉.双目立体测量中多视角深度图同时融合算法[J].计算机辅助设计与图形学学报,2008,20
(11):144621451)
[5]Long Xi,Zhong Yuexian,Li Renju,et al.32D surface
integration in structured light32D scanning[J].Journal of
Tsinghua University:Science and Technology,2002,42(4): 4772480(in Chinese)
(龙 玺,钟约先,李仁举,等.结构光三维扫描测量的三维拼接技术[J].清华大学学报:自然科学版,2002,42(4): 4772480)
[6]Wei Hu,Liu Shenglan,Zhang Liyan,et al.Reference point
based registration algorit hm for binocular stereo vision system [J].China Mechanical Engineering,2009,20(14):17362 1740(in Chinese)
(韦 虎,刘胜兰,张丽艳,等.双目立体测量系统中的标记点配准算法研究[J].中国机械工程,2009,20(14):17362 1740)
[7]Salvi J,Matabosch C,Fofi D,et al.A review of recent range
image registration met hods wit h accuracy evaluation[J].
Image and Vision Computing,2007,25(5):5782596
[8]ZitováB,Flusser J.Image registration met hods:a survey
[J].Image and Vision Computing,2003,21(11):97721000 [9]Lindeberg T.Feature detection wit h automatic scale selection
[J].International Journal of Computer Vision,1998,30(2): 792116
[10]Lowe D G.Distinctive image features from scale2invariant
keypoint s[J].International Journal of Computer Vision, 2004,60(2):912110
[11]Mikolajczyk K,Tuytelaars T,Schmid C,et al.A comparison
of affine region detectors[J].International Journal of
Computer Vision,2005,65(1Π2):43272
[12]Lee C H,Varshney A,J acobs D W.Mesh saliency[J].
ACM Transactions on Graphics,2005,24(3):6592666 [13]Schlatt mann M.Int rinsic features on surfaces[C]ΠΠ
Proceedings of t he10t h Central European Seminar on Computer Graphics,Vienna,2006:1692176
[14]Novatnack J,Nishino K.Scale2dependent3D geometric
features[C]ΠΠProceedings of t he11t h IEEE International Conference on Computer Vision,Rio de J aneiro,2007:14220 [15]Dong C S,Wang G Z.Curvatures estimation on triangular
mesh[J].Journal of Zhejiang University SCIENCE,2005, 6A(Suppl.I):1282136
[16]Qian Sen,Zhu Jianying.Improved SIF T2based bidirectional
image matching algorit hm[J].Mechanical Science and
Technology for Aerospace Engineering,2007,26(9):11792 1182(in Chinese)
(骞 森,朱建英.基于改进的SIF T特征的图像双向匹配算法[J].机械科学与技术,2007,26(9):117921182)
166
第4期韦 虎,等:基于SIFT图像特征匹配的多视角深度图配准算法
图像匹配的主要方法分析 在我国的图像处理中，有很多的关键技术正在不断的发展和创新之中。这些相关技术的发展在很大程度上推动了我国图像处理事业的发展。作为图像处理过程中的关键技术，图像匹配技术正在受到越来越多的关注。文章针对图像匹配的主要方法进行详细的论述，希望通过文章的阐述和分析能够为我国的图像匹配技术的发展和创新贡献微薄力量，同时也为我国图像处理技术的发展贡献力量。 标签：图像处理；图像匹配；特征匹配；方法 在我国的图像处理技术中，图像的匹配技术不仅仅是其中的重要组成部分，同时还是很多图像技术的发展创新的技术基础。例如图像技术中的立体视觉技术；图像技术中的运动分析技术以及图像技术中的数据融合技术等。通过上述内容可以看出，在我国的图像技术中，图像匹配技术具有非常广泛的应用。随着我国的相关技术不断的创新和发展，对于图像匹配技术的要求也是越来越高。这样就要求我国的图像匹配技术有更深层次的研究和发展。我国现阶段的研究主要是针对图像匹配过程中的匹配算法进行研究，希望借助研究能够更加有效的提升在实际的工作应用中的图像质量，同时也能够在很大程度上提升图像处理的图像分别率。文章的主要陈述点是通过图像匹配技术的具体方法进行优点和缺点的分析，通过分析优点和缺点来论述我国图像处理技术中的图像匹配技术的发展方向以及改进措施。近些年出现了很多的图像匹配方法，针对现阶段的新方法以及新的研究思路我们在实际的应用过程中要有一个非常清醒的选择。文章针对这一问题主要有三个内容的阐述。第一个是图像匹配技术的算法融合；第二个是图像匹配技术中的局部特征算法；最后一个是图像匹配技术中的模型匹配具体算法。 1 现阶段在世界范围内较为经典的图像匹配技术的算法 关于现阶段在世界范围内的较为经典的图像匹配技术的算法的阐述，文章主要从两个方面进行分析。第一个方面是ABS图像匹配算法。第二个方面是归一化相互关图像匹配算法。下面进行详细的论述和分析。 （1）算法一：ABS图像匹配算法。ABS图像匹配算法最主要的原理就是要使用模板的图像以及相应的匹配图像的搜索用窗口之间的转换差别来显示两者之间的关联性。图像匹配的大小在数值上等同于模板图像的窗口滑动顺序。窗口的每一次滑动都会引起模板图像的匹配计算。现阶段ABS的算法主要有三个，如下： 在选择上述三种计算方法的过程中要根据实际情况社情相应的阀值，否则会出现很高的失误率。上述的三种算法使用范围较狭窄。只使用与等待匹配的图像在模板影像的计算。 （2）算法二：归一化相互关图像匹配算法。归一化相互关的图像匹配算法在现阶段是较为经典的算法。通常专业的称法为NC算法。此计算方法主要是采
诚信声明 本人声明： 我所呈交的本科毕业设计论文是本人在导师指导下进行的研究工作及取得的研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不包含其他人已经发表或撰写过的研究成果。与我一同工作的同志对本研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。本人完全意识到本声明的法律结果由本人承担。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名：日期：2010 年05 月20日
毕业设计（论文）任务书 设计（论文）题目： 学院：专业：班级： 学生指导教师（含职称）：专业负责人： 1．设计（论文）的主要任务及目标 (1) 了解图象匹配技术的发展和应用情况，尤其是基于特征的图象匹配技术的发展和应用。 (2) 学习并掌握图像匹配方法，按要求完成算法 2．设计（论文）的基本要求和内容 （1）查阅相关中、英文文献，完成5000汉字的与设计内容有关的英文资料的翻译。（2）查阅15篇以上参考文献，其中至少5篇为外文文献，对目前国内外图象匹配技术的发展和应用进行全面综述。 （3）学习图象匹配算法，尤其是基于特征的图象匹配算法。 （4）实现并分析至少两种基于特征的图象匹配算法，并分析算法性能。 3．主要参考文献 [1]谭磊, 张桦, 薛彦斌．一种基于特征点的图像匹配算法[J]．天津理工大学报，2006， 22(6)，66-69． [2]甘进，王晓丹，权文．基于特征点的快速匹配算法[J]．电光与控制，2009，16(2)， 65-66． [3]王军，张明柱．图像匹配算法的研究进展[J]．大气与环境光学学报，2007，2(1)， 12-15．
图像匹配与拼接 分匹配和拼接两部分 一、匹配 当然匹配的方法，有sift，surf什么的，这里主要就介绍一下我自己的方法啦！ 特征点提取是必须的，不然搜索范围太大哇！并且可能不可靠，所以特征点提取是必须的。什么点适合做特征点呢？这方面的论文很多啦，主要还是看你用什么方法匹配了，如果是用互相关作为相似性准则的话，那自相关系数随各个方向变化大的点就适合作特征点了，当然还要考虑稳定性，即特征点应该不太受光照、噪声、缩放、旋转等的影响，这样的才是好的特征点。当然，如果确定了应用坏境，不一定要满足不受上四个因素影响的，比如平行的双目匹配、全景图的匹配等，具体问题具体分析吧！角点特征是个人比较喜欢的特征。这里我自己定义了一种局部特征，效果还行，匹配采用互相关为准则的匹配，大概效果如下： 目测这几个匹配点还是正确的哇！在一些应用中，可能需要的匹配点数相当多，这就需要较密集的匹配了。密集的匹配可以根据初始的匹配结果估计搜索范围，这可以加速搜索，同时也要提取更多的特征点呀！话不多说了，下面是密集的匹配：
虽然这样的密度对于三维重构来说还不够，但对于一般的图像拼接来说足够了。匹配完了，下面就要将第二步了。 二、矫正 匹配好两幅图像了，接下来干啥呢？把它们对准呗。可惜了，两幅图像之间不但存在平移，还存在旋转缩放什么的，更复杂的，可能还存在所谓的3D变换，那就复杂啦！不管怎么样，所谓的对准，也就是矫正，总是基于一定的模型的，即基于相机拍摄两幅图像的相对姿态。对于全景图拼接（个人觉得是最简单的且较实用的拼接），需要根据相机焦距或者视场角投影到柱面上，然后两幅图像间的位置就只有一维的平移关系了。但是这对拍摄的相机也是有要求的，就是要保证拍摄两幅图像时，物防焦点是重合的，这样才能根据稀疏的几个点确定所有重叠区域内点的相对位置呀！但实际中很难做到物方焦点重合，比如数码相机或者所谓的智能手机的全景图拍摄，一般人都是拿着相机或者手机绕人旋转，而非绕物方焦点旋转拍摄的，这样拼接起来是绝对有误差的呀！特别是拼接近景，误差就更大了，远景还好。怎么克服这个缺点呢？简单的改进方法就是绕着摄像头旋转吧，虽然这也不是严格绕物方焦距旋转，但起码误差小得多啦，拼接的效果当然也就好得多了，可以试一试哦！ 不扯了，第二种模型就是认为两幅图像间存在的变换关系是有2D旋转、缩放、平移的，可以通过一个旋转、缩放、平移矩阵来矫正，这个也不难，但是应用范围却相当有限，不详说了。 第三种模型就是不用模型，或者说认为两幅图像间的对应点存在的是一种线性变换关系，这样只要解一个线性方程组就可以了，似乎也挺简单的。但可惜的是，不是任给的两幅图像间都只存在线性变换呀！它可能是一个3D的线性变换，那就麻烦了，这个必须需要密匹配呀！不然就一定是有误差的，即不能通过稀疏的匹配点来矫正两幅图像的所有对应点的。 还有更多的模型，比如各方位的全景图，需要投影到球面上的哇！不过这个模型也不难。最难的当然是拍摄两幅图像时，相机不同，相机姿态也不同了，这个是很有挑战的，我也很惧怕这个。下面展示三种矫正结果： 1、2D线性模型： 2D矫正，认为匹配点之间存在线性变换，X=ax+by+c，Y=dx+ey+e这样的模型，业内称之放射变换，其中x，y是第一幅点的坐标，X,Y是对应的第二幅图像中的点坐标，使用最小二乘法计算a、b、c、d、e、f，第二幅图相对于第一幅图矫正的结果就是这样的了
SIFT 特征提取算法总结 主要步骤 1)、尺度空间的生成； 2)、检测尺度空间极值点； 3)、精确定位极值点； 4)、为每个关键点指定方向参数； 5)、关键点描述子的生成。 L(x,y,σ), σ= 1.6 a good tradeoff
D(x,y,σ), σ= 1.6 a good tradeoff
关于尺度空间的理解说明：图中的2是必须的，尺度空间是连续的。在 Lowe 的论文中， 将第0层的初始尺度定为1.6，图片的初始尺度定为0.5. 在检测极值点前对原始图像的高斯平滑以致图像丢失高频信息，所以Lowe 建议在建立尺度空间前首先对原始图像长宽扩展一倍，以保留原始图像信息，增加特征点数量。尺度越大图像越模糊。 next octave 是由first octave 降采样得到（如2） ， 尺度空间的所有取值，s为每组层数，一般为3~5 在DOG尺度空间下的极值点 同一组中的相邻尺度（由于k的取值关系，肯定是上下层）之间进行寻找
在极值比较的过程中，每一组图像的首末两层是无法进行极值比较的，为了满足尺度 变化的连续性，我们在每一组图像的顶层继续用高斯模糊生成了 3 幅图像， 高斯金字塔有每组S+3层图像。DOG金字塔每组有S+2层图像.
If ratio > (r+1)2/(r), throw it out (SIFT uses r=10) 表示DOG金字塔中某一尺度的图像x方向求导两次 通过拟和三维二次函数以精确确定关键点的位置和尺度（达到亚像素精度）？
直方图中的峰值就是主方向，其他的达到最大值80%的方向可作为辅助方向 Identify peak and assign orientation and sum of magnitude to key point The user may choose a threshold to exclude key points based on their assigned sum of magnitudes. 利用关键点邻域像素的梯度方向分布特性为每个关键点指定方向参数，使算子具备 旋转不变性。以关键点为中心的邻域窗口内采样，并用直方图统计邻域像素的梯度 方向。梯度直方图的范围是0～360度，其中每10度一个柱，总共36个柱。随着距中心点越远的领域其对直方图的贡献也响应减小.Lowe论文中还提到要使用高斯函 数对直方图进行平滑，减少突变的影响。
本文基于相关性分析来实现图像匹配 第一步：读取图像。 分别读取以下两幅相似的图片，显示效果如下： 第二步：选择一副图像的子区域。用户可以通过鼠标选择需要截取的图像部分，用于匹配。随机选取图片的一块区域，如下图：
第三步：使用相关性分析两幅图像 采用协方差的方式计算相关系数，分析图片的相似性。 1．协方差与相关系数的概念 对于二维随机变量(,)X Y ，除了关心它的各个分量的数学期望和方差外，还需要知道这两个分量之间的相互关系，这种关系无法从各个分量的期望和方差来说明，这就需要引进描述这两个分量之间相互关系的数字特征——协方差及相关系数。 若X Y 与相互独立,则()( )0 Y E X EX Y EY σ--???? =≠;若()()0E X EX Y EY --≠????,则表 示X 与Y 不独立,X 与Y 之间存在着一定的关系 设 (,)X Y 是二维随机变量， 则称()()E X EX Y EY --????为X 与Y 的协方差（Covariance ），记为 ()cov ,X Y 或XY σ，即 ()()()cov ,XY X Y E X EX Y EY σ==--???? 若 0X σ≠ 且0Y σ=≠，则称 XY XY X Y σρσσ== 为X 与Y 的相关系数（Correlation Coefficient ）。()c o v ,X Y 是 有量纲的量，而XY ρ则是无量纲的量．协方差常用下列公式计算
()() =-? cov,X Y E XY EX EY 2．用全搜索和协方差计算截取图片与另外一幅图片的各点的相似度。c=normxcorr2(sub_I1(:,:,1),I2(:,:,1)); 第四步：找到整幅图像的偏移。 [max_c,imax]=max(abs(c(:))); [ypeak,xpeak]=ind2sub(size(c),imax(1)); [m,n]=size(sub_I1); xbegin=xpeak-n+1; ybegin=ypeak-m+1; xend=xpeak; yend=ypeak; 从原图像提取匹配到的图像 extracted_I1=I2(ybegin:yend,xbegin:xend,:); 第五步：显示匹配结果。 相关性匹配图： 找出峰值即最相似区域的中心
研究配准进两年的时间，有幸看到一个技术文档，做了一下的总结，如有不妥之处敬请大家谅解，多提出意见 废话不多说，书归正传！ 这里主要讲解的是多模态或者说是多序列MRI图像配准。采用的图片是人体膝盖图。配准暂且分为五部 Step1. 下载图片 Step2. 初始配准（粗配准） Step3. 提高配准精度 Step4. 利用初始条件提高配准精度配准 Step5. 结果满意不满意，你说了算 下面一一详细说明以上几个步骤！ 一，下载图片 这里采用的图片是matlab子带的两张MR膝盖图， “knee1.dcm”作为参考图像，"knee2.dcm"为浮动图像！ Plain Text code ? 1 2 fixed = dicomread('knee1.dcm'); % 读参考图像fixed moving = dicomread('knee2.dcm'); % 读浮动图像moving 可能接下来大家关注的问题就是这两幅图像到底有什么区别，这种区别又有多大的可视化程度，下面就为推荐两个比较好用的函数用于观测两幅图像的区别。Plain Text code ? 1 2 figure, imshowpair(moving, fixed, 'method'); title('Unregistered'); imshowpair函数就是指以成双成对的形式显示图片，其中一个重要的参数就是‘method’，他又4个选择 （1）‘falsecolor’字面意思理解就是伪彩色的意思了，其实就是把两幅图像的差异用色彩来表示，这个是默认的参数。 （2）‘blend’这是一种混合透明处理类型，技术文档的翻译是 alpha blending，大家自己理解吧。 （3）‘diff’这是用灰度信息来表示亮度图像之间的差异，这是对应 ‘falsecolor’的一种方式。 （4）参数‘monotage’可以理解成‘蒙太奇’，这是一种视频剪辑的艺术手法，其实在这里我们理解成拼接的方法就可以了。 为什么在这里罗里吧嗦的说这么多的显示呢，大家知道"人靠衣装，美靠...."(就不多说了吧)，总之就是一个好的视觉效果能给人以耳目一新的效果。
SIFT 特征点匹配算法 基于SIFT 方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： ① 尺度空间极值检测（Scale-space extrema detection ）； ② 精确关键点定位（Keypoint localization ） ③ 关键点主方向分配（Orientation assignment ） ④ 关键点描述子生成（Keypoint descriptor generation ） ⑤ 比较描述子间欧氏距离进行匹配（Comparing the Euclidean distance of the descriptors for matching ） 1.1 尺度空间极值检测 特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。 Koenderink 和Lindeberg 已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：(,,)L x y σ，是由可变尺度的高斯函数(,,)G x y σ与输入图像(,)I x y 卷积得到，即： ),(),,(),,(y x I y x G y x L *=σσ （1.1） 其中：2222/)(221 ),,(σπσσy x e y x G +-= 在实际应用中，为了能相对高效地计算出关键点的位置，建议使用的是差分高斯函数（difference of Gaussian ）(,,)D x y σ。其定义如下： ) ,,(),,() ,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= （1.2） 如上式，D 即是两个相邻的尺度的差（两个相邻的尺度在尺度上相差一个相乘系数k ）。
二分图的最优匹配（KM算法） KM算法用来解决最大权匹配问题：在一个二分图内，左顶点为X，右顶点为Y，现对于每组左右连接XiYj有权wij，求一种匹配使得所有wij的和最大。 基本原理 该算法是通过给每个顶点一个标号（叫做顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。设顶点Xi的顶标为A[ i ]，顶点Yj的顶标为B[ j ]，顶点Xi与Yj之间的边权为w[i,j]。在算法执行过程中的任一时刻，对于任一条边(i,j)，A[ i ]+B[j]>=w[i,j]始终成立。 KM算法的正确性基于以下定理： 若由二分图中所有满足A[ i ]+B[j]=w[i,j]的边(i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。 首先解释下什么是完备匹配，所谓的完备匹配就是在二部图中，X点集中的所有点都有对应的匹配或者是 Y点集中所有的点都有对应的匹配，则称该匹配为完备匹配。 这个定理是显然的。因为对于二分图的任意一个匹配，如果它包含于相等子图，那么它的边权和等于所有顶点的顶标和；如果它有的边不包含于相等子图，那么它的边权和小于所有顶点的顶标和。所以相等子图的完备匹配一定是二分图的最大权匹配。 初始时为了使A[ i ]+B[j]>=w[i,j]恒成立，令A[ i ]为所有与顶点Xi关联的边的最大权，B[j]=0。如果当前的相等子图没有完备匹配，就按下面的方法修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止。 我们求当前相等子图的完备匹配失败了，是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，它的叶子结点全部是X顶点。现在我们把交错树中X顶点的顶标全都减小某个值d，Y顶点的顶标全都增加同一个值d，那么我们会发现： 1）两端都在交错树中的边(i,j)，A[ i ]+B[j]的值没有变化。也就是说，它原来属于相等子图，现在仍属于相等子图。 2）两端都不在交错树中的边(i,j)，A[ i ]和B[j]都没有变化。也就是说，它原来属于（或不属于）相等子图，现在仍属于（或不属于）相等子图。 3）X端不在交错树中，Y端在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所增大。它原来不属于相等子图，现在仍不属于相等子图。 4）X端在交错树中，Y端不在交错树中的边(i,j)，它的A[ i ]+B[j]的值有所减小。也就说，它原来不属于相等子图，现在可能进入了相等子图，因而使相等子图得到了扩大。（针对之后例子中x1->y4这条边） 现在的问题就是求d值了。为了使A[ i ]+B[j]>=w[i,j]始终成立，且至少有一条边进入相等子图，d应该等于： Min{A[i]+B[j]-w[i,j] | Xi在交错树中，Yi不在交错树中}。 改进 以上就是KM算法的基本思路。但是朴素的实现方法，时间复杂度为O(n4)——需要找O(n)次增广路，每次增广最多需要修改O(n)次顶标，每次修改顶标时由于要枚举边来求d值，复杂度为O(n2)。实际上KM算法的复杂度是可以做到O(n3)的。我们给每个Y顶点一个“松弛量”函数slack，每次开始找增广路时初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slack[j]变成原值与A[ i ]+B[j]-w[i,j]的较小值。这样，在修改顶标时，取所有不在交错树中的Y 顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的不在交错树中的Y顶点的slack值都减去d（因为：d的定义为 min{ (x,y)| Lx(x)+ Ly(y)- W(x,y), x∈ S, y? T }
图像特征特点及常用的特征提取与匹配方法 常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。 一颜色特征 （一）特点：颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。另外，仅使用颜色特征查询时，如果数据库很大，常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法，其优点是不受图像旋转和平移变化的影响，进一步借助归一化还可不受图像尺度变化的影响，基缺点是没有表达出颜色空间分布的信息。 （二）常用的特征提取与匹配方法 （1） 颜色直方图 其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。 最常用的颜色空间：RGB颜色空间、HSV颜色空间。 颜色直方图特征匹配方法：直方图相交法、距离法、中心距法、参考颜色表法、累加颜色直方图法。 （2） 颜色集 颜色直方图法是一种全局颜色特征提取与匹配方法，无法区分局部颜色信息。颜色集是对颜色直方图的一种近似首先将图像从RGB颜色空间转化成视觉均衡 的颜色空间（如HSV 空间），并将颜色空间量化成若干个柄。然后，用色彩自动分割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引，从而将图像表达为一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集之间的距离和色彩区域的空间关系 （3） 颜色矩
图像处理技术——模板匹配算法 左力2002．3． 认知是一个把未知与已知联系起来的过程。对一个复杂的视觉系统来说，它的内部常同时存在着多种输入和其它知识共存的表达形式。感知是把视觉输入与事前已有表达结合的过程，而识别也需要建立或发现各种内部表达式之间的联系。 匹配就是建立这些联系的技术和过程。建立联系的目的是为了用已知解释未知。 章毓晋《图像工程下册》P.163 一．模板匹配的基本概念 模板就是一幅已知的小图像。模板匹配就是在一幅大图像中搜寻目标，已知该图中有要找的目标，且该目标同模板有相同的尺寸、方向和图像，通过一定的算法可以在图中找到目标，确定其坐标位置。 以8位图像(其1个像素由1个字节描述)为例，模板T( m ? n个像素)叠放在被搜索图S( W ? H个像素)上平移，模板覆盖被搜索图的那块区域叫子图Sij。i，j为子图左上角在被搜索图S上的坐标。搜索范围是： 1 ≤ i ≤ W – M 1 ≤ j ≤ H – N 通过比较T和Sij的相似性，完成模板匹配过程。 注意：图像的数据是从下到上、从左到右排列的。 可以用下式衡量T和Sij相似性： ∑∑ = =- = N n ij M m n m T n m S j i D 12 1 )] , ( ) , ( [ ) ,(被搜索图 S 模板 T m i {
∑∑ ∑∑ ∑∑ ======+?-=N n M m N n ij M m N n ij M m n m T n m T n m S n m S 1 2 1 1 1 1 2 1 )] ,([),(),(2)],([ 上式的第一项为子图的能量，第三项为模板的能量，都与模板匹配无关。第二项是模板和子图的互相关，随( i, j )而改变。当模板和子图匹配时，该项有极大值。将其归一化，得模板匹配的相关系数： ∑∑∑∑∑∑======?= N n M m N n ij M m N n ij M m n m T n m S n m T n m S j i R 1 2 1 1 2 1 1 1 )] ,([)],([) ,(),(),( 当模板和子图完全一样时，相关系数R( i, j ) = 1。在被搜索图S 中完成全部搜索后，找出R 的最大值Rmax( im, jm )，其对应的子图Simjm 即为匹配目标。显然，用这种公式做图像匹配计算量大、速度较慢。 另一种算法是衡量T 和Sij 的误差，其公式为： ∑∑ ==-=N n ij M m n m T n m S j i E 1 1 |),(),(|),( E( i, j )为最小值处即为匹配目标。为提高计算速度，取一个误差阈值E 0，当E( i, j )> E 0时就停止该点的计算，继续下一点计算。 试验结果如下： 注：以上试验是在赛扬600 PC 机上用VC6.0进行的。 结果表明：被搜索图越大，匹配速度越慢；模板越小，匹配速度越快。误差法速度较快，阈值的大小对匹配速度影响大，和模板的尺寸有关。 二．改进模板匹配算法 我在误差算法的基础上设计了二次匹配误差算法： 第一次匹配是粗略匹配。取模板的隔行隔列数据，即四分之一的模板数据，在被搜索图上进行隔行隔列扫描匹配，即在原图的四分之一范围内匹配。由于数据量大幅度减少，匹配速度显著提高。 为了合理的给出一个误差阈值E0，我设计了一个确定误差阈值E0的准则： E 0 = e 0 * (m+1)/2 * (n+1)/2
二 特征点提取算法 1、基于SIFT （Scale Invariant Feature Transform ）方法的图像特征匹配 参看David G. Lowe 的“Distinctive Image Features from Scale-Invariant Keypoints ” 基于SIFT 方法的图像特征匹配可分为特征提取和特征匹配两个部分，可细化分为五个部分： ① 尺度空间极值检测（Scale-space extrema detection ）； ② 精确关键点定位（Keypoint localization ） ③ 关键点主方向分配（Orientation assignment ） ④ 关键点描述子生成（Keypoint descriptor generation ） ⑤ 比较描述子间欧氏距离进行匹配（Comparing the Euclidean distance of the descriptors for matching ） 1.1 尺度空间极值检测 特征关键点的性质之一就是对于尺度的变化保持不变性。因此我们所要寻找的特征点必须具备的性质之一，就是在不同尺度下都能被检测出来。要达到这个目的，我们可以在尺度空间内寻找某种稳定不变的特性。 Koenderink 和Lindeberg 已经证明，变换到尺度空间唯一的核函数是高斯函数。因此一个图像的尺度空间定义为：(,,)L x y σ，是由可变尺度的高斯函数(,,)G x y σ与输入图像(,)I x y 卷积得到，即： ),(),,(),,(y x I y x G y x L *=σσ （1.1） 其中：2222/)(221 ),,(σπσσy x e y x G +-= 在实际应用中，为了能计算的相对高效，所真正使用的是差分高斯尺度空间（difference of Gaussian ）(,,)D x y σ。其定义如下： ) ,,(),,() ,()),,(),,((),,(σσσσσy x L k y x L y x I y x G k y x G y x D -=*-= （1.2） 如上式，D 即是由两个相邻的尺度的差（两个相邻的尺度在尺度上相差一个相乘系数k ）。
图像特征特点及其常用的特征提取与匹配方法 [ 2006-9-22 15:53:00 | By: 天若有情 ] 常用的图像特征有颜色特征、纹理特征、形状特征、空间关系特征。 一颜色特征 （一）特点：颜色特征是一种全局特征,描述了图像或图像区域所对应的景物的表面性质。一般颜色特征是基于像素点的特征，此时所有属于图像或图像区域的像素都有各自的贡献。由于颜色对图像或图像区域的方向、大小等变化不敏感，所以颜色特征不能很好地捕捉图像中对象的局部特征。另外，仅使用颜色特征查询时，如果数据库很大，常会将许多不需要的图像也检索出来。颜色直方图是最常用的表达颜色特征的方法，其优点是不受图像旋转和平移变化的影响，进一步借助归一化还可不受图像尺度变化的影响，基缺点是没有表达出颜色空间分布的信息。 （二）常用的特征提取与匹配方法 （1）颜色直方图 其优点在于：它能简单描述一幅图像中颜色的全局分布，即不同色彩在整幅图像中所占的比例，特别适用于描述那些难以自动分割的图像和不需要考虑物体空间位置的图像。其缺点在于：它无法描述图像中颜色的局部分布及每种色彩所处的空间位置，即无法描述图像中的某一具体的对象或物体。 最常用的颜色空间：RGB颜色空间、HSV颜色空间。 颜色直方图特征匹配方法：直方图相交法、距离法、中心距法、参考颜色表法、累加颜色直方图法。 （2）颜色集 颜色直方图法是一种全局颜色特征提取与匹配方法，无法区分局部颜色信息。颜色集是对颜色直方图的一种近似首先将图像从RGB颜色空间转化成视觉均衡的颜色空间（如HSV 空间），并将颜色空间量化成若干个柄。然后，用色彩自动分割技术将图像分为若干区域，每个区域用量化颜色空间的某个颜色分量来索引，从而将图像表达为一个二进制的颜色索引集。在图像匹配中，比较不同图像颜色集之间的距离和色彩区域的空间关系 （3）颜色矩 这种方法的数学基础在于：图像中任何的颜色分布均可以用它的矩来表示。此外，由于颜色分布信息主要集中在低阶矩中，因此，仅采用颜色的一阶矩（m ean）、二阶矩（variance）和三阶矩（skewness）就足以表达图像的颜色分布。（4）颜色聚合向量 其核心思想是：将属于直方图每一个柄的像素分成两部分，如果该柄内的某些像素所占据的连续区域的面积大于给定的阈值，则该区域内的像素作为聚合像素，否则作为非聚合像素。 （5）颜色相关图 二纹理特征 （一）特点：纹理特征也是一种全局特征，它也描述了图像或图像区域所对应景物的表面性质。但由于纹理只是一种物体表面的特性，并不能完全反映出物体的本质属性，所以仅仅利用纹理特征是无法获得高层次图像内容的。与颜色特征不同，纹理特征不是基于像素点的特征，它需要在包含多个像素点的区域中进行统计计算。在模式匹配中，这种区域性的特征具有较大的优越性，不会由于局
SIFT算法分析 1 SIFT 主要思想 SIFT算法是一种提取局部特征的算法，在尺度空间寻找极值点，提取位置，尺度，旋转不变量。 2 SIFT 算法的主要特点： a)SIFT特征是图像的局部特征，其对旋转、尺度缩放、亮度变化保持不变性，对视角变化、仿射变换、噪声也保持一定程度的稳定性。 b)独特性(Distinctiveness)好，信息量丰富，适用于在海量特征数据库中进 行快速、准确的匹配。 c)多量性，即使少数的几个物体也可以产生大量SIFT特征向量。 d)高速性，经优化的SIFT匹配算法甚至可以达到实时的要求。 e)可扩展性，可以很方便的与其他形式的特征向量进行联合。 3 SIFT 算法流程图：
4 SIFT 算法详细 1）尺度空间的生成 尺度空间理论目的是模拟图像数据的多尺度特征。 高斯卷积核是实现尺度变换的唯一线性核，于是一副二维图像的尺度空间定义为： L( x, y, ) G( x, y, ) I (x, y) 其中G(x, y, ) 是尺度可变高斯函数，G( x, y, ) 2 1 2 y2 (x ) 2 e / 2 2 （x，y）是空间坐标，是尺度坐标。大小决定图像的平滑程度，大尺度对应图像的概貌特征，小尺度对应图像的细节特征。大的值对应粗糙尺度(低分辨率)，反之，对应精细尺度(高分辨率)。 为了有效的在尺度空间检测到稳定的关键点，提出了高斯差分尺度空间（DOG scale-space）。利用不同尺度的高斯差分核与图像卷积生成。 D( x, y, ) (G( x, y,k ) G( x, y, )) I ( x, y) L( x, y,k ) L( x, y, ) DOG算子计算简单，是尺度归一化的LoG算子的近似。图像金字塔的构建：图像金字塔共O组，每组有S层，下一组的图像由上一 组图像降采样得到。 图1由两组高斯尺度空间图像示例金字塔的构建，第二组的第一副图像由第一组的第一副到最后一副图像由一个因子2降采样得到。图2 DoG算子的构建： 图1 Two octaves of a Gaussian scale-space image pyramid with s =2 intervals. The first image in the second octave is created by down sampling to last image in the previous
毕业设计（论文）题目基于SIFT特征的图像匹配 姓名张建华 学号0811111101 所在学院理学院 专业班级08信计 指导教师吴颖丹 日期2012 年 6 月 2 日
摘要 当今社会已经进入信息时代，随着计算机技术、通信技术和数学的发展，图像信息处理能力和水平也不断提高，相应的也得到更多关注、研究和更加广泛的应用。图像匹配是处理和解决各种图像信息的基础，已经成为虚拟现实和计算机可视化领域的研究热点。一直以来，研究人员对图像匹配技术进行了大量的研究，推出了许多匹配算法，其中特征匹配算法有着较高的精确度和稳定性。SIFT （Scale Invariant Feature Transform）特征匹配算法是Lowe提出来的用于图像特征匹配的算法，是目前特征匹配领域的热点，对图像的旋转，尺度缩放和亮度变换保持不变，对视角变换，仿射变换保持一定程度的稳定。SIFT特征点是图像的一种尺度不变局部特征点，具有独特性好，信息量丰富，多量性，高速性，可扩展性等特点。正是借助于这些特点，使得传统图像配准中的许多诸如前面提到的共性问题得到了很大程度的改善。该算法首先给出了尺度空间的生成方法，检测出极值点；接下来给出了SIFT特征点的提取步骤和精确定位极值点的方法；然后基于特征点邻域像素的梯度和方向生成了关键点的描述向量；最后根据特征向量给出了匹配方法，提取了SIFT的特征点，并其应用于图像匹配。 本文首先简要介绍了图像匹配所需的基础知识，然后详细介绍了SIFT算法的具体流程。通过大量的实验证明SIFT算法具有较强的匹配能力和鲁棒性，是一种较好的图像匹配算法。 关键字：SIFT; 图像匹配; 尺度空间; 极值点; 特征向量
关于图像匹配的综述 1.图像匹配的背景及定义 1.1图像匹配的背景及意义 图像匹配技术广泛的应用于日常生活中的诸多领域，如医疗诊断中各种医学图片的分析与识别、遥感图片识别、天气预报中的卫星云图识别、指纹识别、人脸识别等。图像匹配技术主要指通过计算机，采用数学技术方法，对获取的图像按照特定目的进行相应的处理。图像匹配技术是人工智能的一个重要分支和应用，随着计算机技术及人工智能技术的发展，图像识别技术逐渐成为人工智能的基础技术之一。它涉及的技术领域相当的广泛，也越来越深入，其基本分析方法也随着数学工具的不断进步而不断发展。现在，图像识别技术的应用范围己经不仅仅局限于视觉的范围，也体现在机器智能和数字技术等方面。 1.2图像匹配的定义 所谓图像匹配是指在一幅(或一批)图像中寻找与给定目标图像相似的图像或者图像区域(子图像)的过程。通常将已知目标图像称为模板图像，而将待搜索图像中可能与它对应的子图称作该模板的待匹配的目标图像。图像匹配是在来自不同时间或者不同视角的同一场景的两幅或多幅图像之间寻找对应关系，该技术隶属于计算机视觉哺领域。图像匹配的具 体应用包括目标或场景识别、在多幅图像中求解3D结构、立体对应和运动跟踪等。由于拍摄时间、拍摄角度、自然环境的变化，多种传感器的使用、传感器本身的缺陷及噪声等影响，拍摄的图像会存在灰度失真和几何畸变。同时，图像预处理过程会引入的误差，这都是导致模板图像与待匹配的目标图像之间通常存在着一定程度上的差异。在这种情况下，如何使匹配算法精度高、正确匹配率高、速度快和抗干扰性强成为人们关心的问题。 2.图像匹配算法的分类 图像匹配算法的选取对图像匹配结果的影响很大。实用的匹配算法不仅要求计算量小，还必须具有良好的抗噪能力和抗几何形变的能力。通常情况下，图像匹配算法可以分为以下两大类：基于灰度相关的匹配算法、基于特征的图像匹配算法。 1) 基于灰度分布的相关匹配算法，也称为基于区域的匹配方法。常见的基于图像灰度的匹配方法有：（1）归一化灰度相关匹配、（2）最小二乘影像匹配、和（3）序贯相似性检测法匹配等。该类算法直接利用整幅图像的灰度信息，建立两幅图像之间的相似性度量，然后采用某种搜索方法，寻找使相似性度量值最大或最小的变换模型的参数值。在灰度及几何畸变
图的匹配 一、什么是图的匹配 1.图的定义 无向图：无向图G 是指非空有限集合V G ，和V G 中某些元素的无序对的集合E G ，构成的二元组(V G ，E G )。V G 称为G 的顶点集，其中的元素称为G 的顶点。E G 称为G 的边集，其中的元素称为G 的边。在不混淆的情况下，有时记V ＝V G ，E ＝E G 。如果V ＝{v 1,…,v n }，那么E 中的元素e 与V 中某两个元素构成的无序对(v i ，v j )相对应，记e ＝v i v j ，或e ＝v j v i 。在分析问题时，我们通常可以用小圆圈表示顶点，用小圆圈之的连线表示边。 二分图：设G 是一个图。如果存在V G 的一个划分X ，Y ，使得G 的任何一条边的一个端点在X 中，另一个端点在Y 中，则称G 为二分图，记作G ＝(X ，Y ，E)。如果G 中X 的每个顶点都与Y 的每个顶点相邻，则称G 为完全二分图。 2.匹配的相关概念 设G ＝(V ，E)是一个图，E M ?，如果M 不含环且任意两边都不相邻，则称M 为G 的一个匹配。G 中边数最多的匹配称为G 的最大匹配。 对于图G ＝(V ，E)，在每条边e 上赋一个实数权w(e)。设M 是G 的一个匹配。定义∑∈=m e e w M w )()(，并称之为匹配M 的权。G 中权最大的匹配称为G 的最大权匹配。如果 对一切，e ∈E ，w(e)=1,则G 的最大权匹配就是G 的最大匹配。 设M 是图G=(V ,E)的一个匹配，v i ∈V 。若v i 与M 中的边相关联，则称v i 是M 饱和点，否则称v i 为M 非饱和点。 如果G 中每个顶点都是M 饱和点，则称M 为G 的完美匹配。 设M 是G 的一个匹配，P 是G 的一条链。如果P 的边交替地一条是M 中的边，一条不是M 中的边，则称P 为M 交错链。类似地，我们可以定义G 的交错圈。易知，G 的交错圈一定是偶圈。 一条连接两个不同的M 非饱和点的M 交错链称为M 增广链。 两个集合S 1与S 2的“异或”操作S 1⊕S 2是指集合S 1⊕S 2＝（S 1∩S 2）\（S 1∪S 2） 容易看出，设M 是G 的匹配，P 是G 中的M 增广链、则M ⊕P 也是G 的匹配，而且1+=⊕M P M 。 图表 1 “异或”操作 可以证明，G 中匹配M 是最大匹配当且仅当G 中没有M 增广链。
第1章绪论 1.1研究背景及意义 数字图像，又称数码图像或数位图像，是二维图像用有限数字数值像素的表示。通常，像素在计算机中保存为二维整数数组的光栅图像，这些值经常用压缩格式进行传输和储存。数字图像可以由许多不同的输入设备和技术生成，例如数码相机、扫描仪、坐标测量机等，也可以从任意的非图像数据合成得到，例如数学函数或者三维几何模型，三维几何模型是计算机图形学的一个主要分支。数字图像处理领域就是研究它们的变换算法。 数字图像处理(Digital Image Processing)是通过计算机对图像进行去除噪声、增强、复原、分割、提取特征等处理的方法和技术。数字图像处理的产生和迅速发展主要受三个因素的影响:一是计算机的发展;二是数学的发展(特别是离散数学理论的创立和完善);三是广泛的农牧业、林业、环境、军事、工业和医学等方面的应用需求的增长。 图像配准(Image registration)就是将不同时间、不同传感器(成像设备)或不同条件下(天候、照度、摄像位置和角度等)获取的两幅或多幅图像进行匹配、叠加的过程，它已经被广泛地应用于遥感数据分析、计算机视觉、图像处理等领域。 图像配准的方法迄今为止，在国内外的图像处理研究领域，已经报道了相当多的图像配准研究工作，产生了不少图像配准方法。总的来说，各种方法都是面向一定范围的应用领域，也具有各自的特点。比如计算机视觉中的景物匹配和飞行器定位系统中的地图匹配，依据其完成的主要功能而被称为目标检测与定位，根据其所采用的算法称之为图像相关等等。 基于灰度信息的图像配准方法一般不需要对图像进行复杂的预先处理，而是利用图像本身具有灰度的一些统计信息来度量图像的相似程度。主要特点是实现简单，但应用范围较窄，不能直接用于校正图像的非线性形变，在最优变换的搜索过程中往往需要巨大的运算量。经过几十年的发展，人们提出了许多基于灰度信息的图像配准方法，大致可以分为三类：互相关法（也称模板匹配法）、序贯相似度检测匹配法、交互信息法。 目前主要图像配准方法有基于互信息的配准方法，基于相关性的配准方法和基于梯度的配准方法。其中基于梯度的方法基本很少单独使用，而作为一个辅助
图像匹配方法总结 图像匹配最早是美国70年代从事飞行器辅助导航系统，武器投射系统的末制导等应用研究中提出的。从80年代以后，其应用已逐步从原来单纯的军事应用扩大到其它领域。随着科学技术的发展，图像匹配技术已经成为现代信息处理领域中的一项极为重要的技术，在许多领域内有着广泛而实际的应用，如：模式识别，自动导航，医学诊断，计算机视觉，图像三维重构、遥感图像处理等领域。图像匹配是这些应用领域的瓶颈问题，目前很多重要的计算机视觉方面的研究都是在假设匹配问题已经得到解决的前提下开展的。因此，对图像匹配做进一步深入的研究有着非常重要的意义。 图像匹配是图像处理领域常见的基础问题, 是在变换空间中寻找一种或多种变换, 使来自不同时间、不同传感器或不同视角的同一场景的两幅或多幅图像在空间上一致。由于拍摄时间、角度、环境的变化、多种传感器的使用和传感器本身的缺陷, 使拍摄的图像不仅受噪声的影响, 而且存在严重的灰度失真和几何畸变。在这种条件下, 匹配算法如何达到精度高、匹配正确率高、速度快、鲁棒性和抗干扰性强以及并行实现成为人们追求的目标。 根据匹配算法的基本思想可将图像匹配方法分成两大类，即基于区域的匹配方法和基于特征的匹配方法。两类方法相比而言，基于特征的匹配方法有计算量小，鲁棒性好，对图像形变不敏感等优点，所以基于特征的匹配方法是目前研究的热点。基于特征的图像匹配方法主要包括三步：特征提取、特征描述和特征匹配。 一、特征提取方法 图像匹配过程中，首先要根据给定的匹配任务和参与匹配图像的数据特性来决定使用何种特征进行匹配。所选取的特征必须要显著，并且易于提取，在参考图像和待配准图像上都要有足够多的分布，另外，所选择的特征必须易于进行后续的匹配。在图像配准中常用的特征有特征点，如拐点、角点；特征线，如边缘曲线、直线段；特征面，如小面元、闭合区域等。 1、Harris算法 基本思想：它是一种基于信号的点特征提取算子。这种算子受信号处理中自相关函数的启发，给出与自相关函数相联系的矩阵M。M阵的特征值是自相关函数的一阶曲率，如果两个曲率值都高，则认为该点是特征点。 实验结果：Harris算子计算量小，能在一定程度上抗尺度变化，当存在较大尺度缩放时稳定性较差。并且该算子对旋转，噪声敏感。 2、SUSAN算法 基本思想：它用圆形模板在图像上移动，若模板内像素的灰度与模板中心像素灰度的差值小于一定阈值，则认为该点与核具有相同的灰度，由满足这样条件的像素组成的局部区域称为“USAN”。根据USAN的尺寸、质心和二阶矩，可检测边缘、角点等特征。 实验结果：SUSAN算子可提取图像边缘和图像特征点，对明显角点提取的能力较强，较适合提取图像边缘上的拐点。SUSAN算子提取的特征点抗图像旋转、噪声影响的效果较好。 3、Harris-Laplace算法 基本思想：该算法首先使用尺度Harris角点算子在尺度空间中的每一幅二维图像中检测特征点，尺度维上获得选择大于某一阂值的局部极值作为候选角点，然后再验证这些点是否在Laplacian算子局部极大值。如果是，则确定为特征点，并将获得极大值的点所在的尺度作为特征尺度。 实验结果：对Harris算法的改进，使其具有更好的尺度不变性。该算法可提取图像特征点，也